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 <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAX_N = 3005, MOD = 1000000007;
typedef long long i64;
i64 f[2][MAX_N];
int L[MAX_N], R[MAX_N], C[MAX_N][MAX_N];
char s[MAX_N];

int main() {
  int N, M;
  
  scanf("%d%d", &N, &M);
  scanf("%s", s + 1);
  
  for (int i = 1; i <= M; ++i) {
    scanf("%d%d", &L[i], &R[i]);
    if (R[i] <= R[i - 1]) i--, M--;
  }
  
  for (int i = 0; i <= N; ++i) {
    C[i][0] = 1;
    for (int j = 1; j <= i; ++j)
      C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
  }
  
  int o = 0, p;
  R[0] = L[1] - 1, f[0][0] = 1, L[M + 1] = N + 1;
  
  for (int i = 1; i <= M; ++i) {
    p = o, o ^= 1;
    memset(f[o], 0, sizeof f[o]);
    int num = 0;
    for (int j = R[i - 1] + 1; j <= R[i]; ++j)
      if (s[j] == '1') num++;
    
    int temp1 = R[i - 1] - L[i] + 1, temp2 = max(R[i] - L[i + 1] + 1, 0);
    
    for (int k1 = 0; k1 <= temp1; ++k1) {
      int num1 = num + k1, num0 = R[i] - L[i] + 1 - num1;
      for (int k2 = 0; k2 <= temp2; ++k2) {
	int rest1 = num1 - k2, rest0 = num0 - temp2 + k2;
	if (rest1 < 0 || rest0 < 0) continue;
	f[o][k2] = (f[o][k2] + C[rest1 + rest0][rest1] * f[p][k1] % MOD) % MOD;
      }
    }
    if (R[i] < L[i + 1] - 1) R[i] = L[i + 1] - 1;
  }

  printf("%lld\n", f[o][0]);
  
  return 0;
}