#include<bits/stdc++.h>
const int N = 3005;
const int mod = 1e9 + 7;
using namespace std;

int n, m, a[N], dp[N][N], cnt[N], Max;
string s;

void add(int&a, int b){
    a += b; if (a >= mod) a -= mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s; s = '.' + s;
    for (int i = 1; i <= n; i++) cnt[i] = cnt[i-1] + (s[i] == '0');
    while (m--){
        int l, r; cin >> l >> r;
        if (r > Max){
            a[l] = r;
            Max = r;
        }
    }
    Max = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++){
        Max = max(Max, a[i]);
        for (int j = 0; j <= i; j++){
            if (Max < i) {
                if (j - (s[i] == '0') >= 0) dp[i][j] = dp[i-1][j - (s[i] == '0')];
            }
            else{
                if (j <= cnt[Max]) add(dp[i][j], dp[i-1][j-1]);
                if (i-j <= Max - cnt[Max]) add(dp[i][j], dp[i-1][j]);
            }
        }
    }
    cout << dp[n][cnt[n]];
}

### Prompt

Please formulate a cpp solution to the following 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

### Response

```cpp
#include<bits/stdc++.h>
const int N = 3005;
const int mod = 1e9 + 7;
using namespace std;

int n, m, a[N], dp[N][N], cnt[N], Max;
string s;

void add(int&a, int b){
    a += b; if (a >= mod) a -= mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> s; s = '.' + s;
    for (int i = 1; i <= n; i++) cnt[i] = cnt[i-1] + (s[i] == '0');
    while (m--){
        int l, r; cin >> l >> r;
        if (r > Max){
            a[l] = r;
            Max = r;
        }
    }
    Max = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++){
        Max = max(Max, a[i]);
        for (int j = 0; j <= i; j++){
            if (Max < i) {
                if (j - (s[i] == '0') >= 0) dp[i][j] = dp[i-1][j - (s[i] == '0')];
            }
            else{
                if (j <= cnt[Max]) add(dp[i][j], dp[i-1][j-1]);
                if (i-j <= Max - cnt[Max]) add(dp[i][j], dp[i-1][j]);
            }
        }
    }
    cout << dp[n][cnt[n]];
}

```