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

Solution:
#include <bits/stdc++.h>

using namespace std;

const int Dim = 5e3 + 5;
const int Mod = 1e9 + 7;

int mx[ Dim ], r[ Dim ], dp[ Dim ][ Dim ], sum[ Dim ];
int n, m, x, y;

char s[ Dim ];

int main() {
  //  freopen ("input.txt", "r", stdin);

    cin >> n >> m >> (s + 1);
    for (int i = 1; i <= n; ++ i) {
        r[ i ] = i;

        sum[ i ] = sum[i - 1];
        if (s[ i ] == '0')
            ++sum[ i ];
    }

    for (int i = 1; i <= m; ++ i) {
        cin >> x >> y;
        r[ x ] = max (r[ x ], y);
    }

    for (int i = 1; i <= n; ++ i) {
        mx[ i ] = max (r[ i ], mx[i - 1]);
    }

    mx[n + 1] = mx[ n ];
    dp[ 1 ][ sum[ r[ 1 ] ] ] = 1;

    for (int i = 1; i <= n; ++ i) {
        for (int j = 0; j <= m; ++ j) {
            if (dp[ i ][ j ] == 0)
                continue;

            int v1 = j;
            int v2 = mx[ i ] - i + 1 - v1;

            int nr1 = sum[ mx[i + 1] ] - sum[ mx[ i ] ];
            if (v1) {
                dp[i + 1][nr1 + j - 1] += dp[ i ][ j ];
                dp[i + 1][nr1 + j - 1] %= Mod;
            }

            if (v2) {
                dp[i + 1][nr1 + j] += dp[ i ][ j ];
                dp[i + 1][nr1 + j] %= Mod;
            }
        }
    }

    cout << dp[n + 1][ 0 ] << '\n';
    return 0;
}