#include<bits/stdc++.h>

using namespace std;

const int N = (int)3e3 + 5, mod = (int)1e9 + 7;
int n, m, rMost[N], dp[N][N], rPref[N], n0Pref[N];
string s;

int add(int _a, int _b) {
    _a += _b;
    if (_a >= mod) _a -= mod;
    return _a;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("test.INP", "r", stdin);

    cin >> n >> m >> s;
    while (m --) {
        int l, r; cin >> l >> r;
        rMost[l] = max(rMost[l], r);
    }

    s = ' ' + s;
    for (int i = 1; i <= n; ++i) {
        rMost[i] = max(rMost[i], i);
        rPref[i] = max(rPref[i - 1], rMost[i]);
        n0Pref[i] = n0Pref[i - 1] + (s[i] == '0');
    }

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int n0 = 0; n0 <= i; ++n0) if (dp[i][n0]) {
            int n1 = i - n0, rem0 = n0Pref[ rPref[i + 1] ] - n0, rem1 = rPref[i + 1] - n0Pref[ rPref[i + 1] ] - n1;
            if (rem0) dp[i + 1][n0 + 1] = add(dp[i + 1][n0 + 1], dp[i][n0]);
            if (rem1) dp[i + 1][n0] = add(dp[i + 1][n0], dp[i][n0]);
        }
    }

    int ans = 0;
    for (int n0 = 0; n0 <= n; ++n0) ans = add(ans, dp[n][n0]);
    cout << ans;

    return 0;
}
/*
110111

011111
101111
110111
111011

011111
101111
110111
111011
111101
111110
*/

### Prompt

Please provide a cpp coded solution to the problem described below:

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>

using namespace std;

const int N = (int)3e3 + 5, mod = (int)1e9 + 7;
int n, m, rMost[N], dp[N][N], rPref[N], n0Pref[N];
string s;

int add(int _a, int _b) {
    _a += _b;
    if (_a >= mod) _a -= mod;
    return _a;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("test.INP", "r", stdin);

    cin >> n >> m >> s;
    while (m --) {
        int l, r; cin >> l >> r;
        rMost[l] = max(rMost[l], r);
    }

    s = ' ' + s;
    for (int i = 1; i <= n; ++i) {
        rMost[i] = max(rMost[i], i);
        rPref[i] = max(rPref[i - 1], rMost[i]);
        n0Pref[i] = n0Pref[i - 1] + (s[i] == '0');
    }

    dp[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int n0 = 0; n0 <= i; ++n0) if (dp[i][n0]) {
            int n1 = i - n0, rem0 = n0Pref[ rPref[i + 1] ] - n0, rem1 = rPref[i + 1] - n0Pref[ rPref[i + 1] ] - n1;
            if (rem0) dp[i + 1][n0 + 1] = add(dp[i + 1][n0 + 1], dp[i][n0]);
            if (rem1) dp[i + 1][n0] = add(dp[i + 1][n0], dp[i][n0]);
        }
    }

    int ans = 0;
    for (int n0 = 0; n0 <= n; ++n0) ans = add(ans, dp[n][n0]);
    cout << ans;

    return 0;
}
/*
110111

011111
101111
110111
111011

011111
101111
110111
111011
111101
111110
*/

```