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-----
5 2
01001
2 4
3 5

-----Sample Output-----
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.

Difficulty: competition

Starter code:

Solutions:
#!/usr/bin/env python3


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)))


def __starting_point():
    main()


__starting_point()

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)

# 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)
    # i番目を置いた後で、1の個数の範囲
    left = max(0,(i+1)-canuse_0[i])
    right = canuse_1[i]
    # 0を使う
    dp[left:right+1] += prev[left:right+1]
    # 1を使う
    left = max(1,left)
    dp[left:right+1] += prev[left-1:right]
    dp %= MOD

answer = dp.sum()
print(answer)

import sys
readline = sys.stdin.readline

MOD = 10**9+7
N, M = list(map(int, readline().split()))
S = list(map(int, readline().strip()))
Query = [tuple([int(x) - 1 for x in 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)
    


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])