Problem:
 Score : 900 points    Problem Statement There is a string S of length N consisting of characters 0 and 1 . You will perform the following operation for each i = 1, 2, ..., m :   Arbitrarily permute the characters within the substring of S starting at the l_i -th character from the left and extending through the r_i -th character.   Here, the sequence l_i is non-decreasing.  How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7) ?      Constraints  2≦N≦3000  1≦M≦3000  S consists of characters 0 and 1 .  The length of S equals N .  1≦l_i < r_i≦N  l_i ≦ l_{i+1}         Input The input is given from Standard Input in the following format:  N  M  S  l_1  r_1 : l_M  r_M       Output Print the number of the possible values for S after the M operations, modulo 1000000007 .        Sample Input 1 5 2
01001
2 4
3 5      Sample Output 1 6  After the first operation, S can be one of the following three: 01001 , 00101 and 00011 .  After the second operation, S can be one of the following six: 01100 , 01010 , 01001 , 00011 , 00101 and 00110 .       Sample Input 2 9 3
110111110
1 4
4 6
6 9      Sample Output 2 26       Sample Input 3 11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11      Sample Output 3 143

Solution (Python):
mod=10**9+7

N,M=map(int,input().split())
L=-1;R=-1
S=input()
ope=[]
for i in range(M):
    l,r=map(int,input().split())
    l-=1;r-=1
    if L<=l and r<=R:
        continue
    else:
        L,R=l,r
        ope.append((l,r))

M=len(ope)
data=[-1]*N
for i in range(M):
    l,r=ope[i]
    for j in range(l,r+1):
        data[j]=i

dp=[[0 for i in range(N+1)] for j in range(N+1)]

for j in range(N+1):
    dp[-1][j]=1

for i in range(N-1,-1,-1):
    id=data[i]
    if id!=-1:
        l,r=ope[id]
        temp1=sum(int(S[k]) for k in range(r+1))
        temp0=r+1-temp1
        for j in range(temp1+1):
            np1=temp1-j
            np0=temp0-(i-j)
            if np1==0:
                if np0>0:
                    dp[i][j]=dp[i+1][j]
            else:
                if np0>0:
                    dp[i][j]=(dp[i+1][j+1]+dp[i+1][j])%mod
                elif np0==0:
                    dp[i][j]=dp[i+1][j+1]
    else:
        if S[i]=="1":
            for j in range(N):
                dp[i][j]=dp[i+1][j+1]
        else:
            for j in range(N+1):
                dp[i][j]=dp[i+1][j]

print(dp[0][0])

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,m = map(int,readline().split())
s = input()
mp = map(int,read().split())

r = list(range(n))
for i,j in zip(mp,mp):
    if r[i-1] < j-1:
        r[i-1] = j-1

for i in range(1,n):
    if r[i] < r[i-1]: r[i] = r[i-1]

zero = [0]*n
one = [0]*n
for i in range(n):
    zero[i] = zero[i-1]
    one[i] = one[i-1]
    if s[i]=="0": zero[i] += 1
    else: one[i] += 1






MOD = 10**9+7
dp = [0]*n
dp[0] = 1
for i in range(n):
    L = max(zero[r[i]] + i - r[i],0)
    R = min(zero[r[i]],i+1)
    ndp = [0]*n

    for i in range(L,R+1):
        if i: ndp[i] += dp[i-1]
        ndp[i] += dp[i]
        ndp[i] %= MOD        
    dp = ndp


    
print(sum(dp))

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc065/tasks/arc065_d

圧倒的dp感

lは非減少なので、 l[i-1] ～l[i] の間が確定する範囲

dp[i][今の区間に残っている1の数] = 並び替えの通り数　でやると
dp推移がO(N^2)になってしまう…

1の位置さえ決まればよい。
あらかじめ、それぞれの1に関して、移動しうる最小のindexと最大のindexを前計算
→どうやって？
→heapといもす法で、最小・最大値管理しつつ

あとはdp中に一点取得、区間加算がO(N)で出来れば、O(N**2)で解ける
→dp[i個目までの1を処理][右端にある1のindex]
とし、最後に累積和で区間加算する→DP推移はO(N)なのでおｋ

→なんか違う？
→1をもってける範囲の右端が実際より短くなっているのが原因


"""
from collections import deque
import heapq
N,M = map(int,input().split())
S = input()
"""
lri = deque([])
rpick = [ [] for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    lri.append([l-1,r-1,i])
    rpick[r].append(i)

lheap = []
rheap = []
state = [False] * M

LRlis = []

for i in range(N):

    while len(lri) > 0 and lri[0][0] == i: 
        l,r,ind = lri.popleft()
        heapq.heappush(lheap,[l,ind])
        heapq.heappush(rheap,[-1*r,ind])

    for pickind in rpick[i]:

        state[pickind] = True

    while len(lheap) > 0 and state[ lheap[0][1] ]:
        heapq.heappop(lheap)
    while len(rheap) > 0 and state[ rheap[0][1] ]:
        heapq.heappop(rheap)

    if S[i] == "1":

        if len(lheap) == 0 or len(rheap) == 0:
            LRlis.append([i,i])
        else:
            LRlis.append([lheap[0][0] , -1 * rheap[0][0] ])

"""
lri = []
for i in range(M):
    l,r = map(int,input().split())
    lri.append([l-1,r-1,i])
lri.append([N,float("inf"),float("inf")])

nexvisit = 0
onenum = 0
LRlis = []
LRlisind = 0
r = 0
for loop in range(M):
    
    l,nr,tempi = lri[loop]
    r = max(nr,r)
    nexl = lri[loop+1][0]
    

    for i in range( max(l,nexvisit) , r+1 ):
        if S[i] == "1":
            LRlis.append([l,None])
            onenum += 1
            nexvisit = max(nexvisit,i+1)
    if r-nexl+1 < onenum:

        for i in range(min(onenum , onenum - (r-nexl+1))):
            LRlis[LRlisind][1] = r-onenum+1
            onenum -= 1
            LRlisind += 1
            
mod = 10**9+7
dp = [0] * (N+1)


for i in range(len(LRlis)):

    

    l,r = LRlis[i]

    ndp = [0] * (N+1)

    if i == 0:
        ndp[l] += 1
        ndp[r+1] -= 1
    else:

        for v in range(r):

            ndp[max(l,v+1)] += dp[v]
            ndp[r+1] -= dp[v]

    for j in range(N):
        ndp[j+1] += ndp[j]
        ndp[j] %= mod
        ndp[j+1] % mod

    dp = ndp


print (sum(dp[0:N]) % mod)

Solution (Python):
import sys
readline = sys.stdin.readline

MOD = 10**9+7
N, M = map(int, readline().split())
S = list(map(int, readline().strip()))
Query = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(M)]

PP = S.count(1)

Li = [None]*PP
Ri = [None]*PP

T1 = S[:]
for l, r in Query:
    cnt = 0
    for i in range(l, r+1):
        cnt += T1[i]
    for i in range(l, l+cnt):
        T1[i] = 1
    for i in range(l+cnt, r+1):
        T1[i] = 0
T2 = S[:]
for l, r in Query:
    cnt = 0
    for i in range(l, r+1):
        cnt += 1 - T2[i]
    for i in range(l, l+cnt):
        T2[i] = 0
    for i in range(l+cnt, r+1):
        T2[i] = 1

cnt = 0
for i in range(N):
    if T1[i]:
        Li[cnt] = i
        cnt += 1
cnt = 0
for i in range(N):
    if T2[i]:
        Ri[cnt] = i+1
        cnt += 1

dp = [0]*N
for i in range(Li[0], Ri[0]):
    dp[i] = 1

for j in range(1, PP):
    dp2 = [0] + dp[:-1]
    for i in range(1, N):
        dp2[i] = (dp2[i]+dp2[i-1])%MOD
    for i in range(Li[j]):
        dp2[i] = 0
    for i in range(Ri[j], N):
        dp2[i] = 0
    dp = dp2[:]
res = 0
for d in dp:
    res = (res+d)%MOD
print(res)

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

MOD = 10**9 + 7

N,M = map(int,input().split())
S = np.array(list(input().rstrip()),dtype='U1')
LR = [[int(x) for x in input().split()] for _ in range(M)]

cnt_0 = (S=='0').cumsum()
cnt_1 = (S=='1').cumsum()
canuse_0 = cnt_0
canuse_1 = cnt_1
for L,R in LR:
    canuse_0[L-1] = max(canuse_0[L-1],cnt_0[R-1])
    canuse_1[L-1] = max(canuse_1[L-1],cnt_1[R-1])
np.maximum.accumulate(canuse_0,out=canuse_0)
np.maximum.accumulate(canuse_1,out=canuse_1)


dp = np.zeros(N+1,dtype=np.int64)
dp[0] = 1
for i in range(N):
    prev = dp
    dp = np.zeros(N+1,dtype=np.int64)
    
    left = max(0,(i+1)-canuse_0[i])
    right = canuse_1[i]
    
    dp[left:right+1] += prev[left:right+1]
    
    left = max(1,left)
    dp[left:right+1] += prev[left-1:right]
    dp %= MOD

answer = dp.sum()
print(answer)

Solution (Python):



M = 10 ** 9 + 7


def solve(n, m, s, lst):

    cnt = [0] * n
    t = 0
    for i in range(n):
        if s[i] == '1':
            t += 1
        cnt[i] = t


    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = 0
    j = 0
    for i in range(n):
        while j < m:
            lj, rj = lst[j]
            if lj <= i:
                r = max(r, rj)
                j += 1
            else:
                break
        if r <= i:
            c = cnt[i]
            if 0 < c:
                dp[i + 1][cnt[i]] = (dp[i][c] + dp[i][c - 1]) % M
            else:
                dp[i + 1][0] = dp[i][0]
        else:
            for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                if 0 < k:
                    dp[i + 1][k] = (dp[i][k] + dp[i][k - 1]) % M
                else:
                    dp[i + 1][0] = dp[i][0]

    return dp[n][cnt[n - 1]]


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    lst = []
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        lst.append((l, r))

    print(solve(n, m, s, lst))


if __name__ == '__main__':
    main()