Problem: 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.

Examples

Input

5 2
01001
2 4
3 5


Output

6


Input

9 3
110111110
1 4
4 6
6 9


Output

26


Input

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11


Output

143

Solution (in PYTHON3):

Solution:
# coding: utf-8
# Your code here!
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


#print(r)
#print(s)
#print(zero)

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(L,R,r[i],zero[r[i]],dp)
print(sum(dp))