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 <cstring>
#include <cstdlib>
#include <cassert>
#include <cctype>
#include <algorithm>
#include <functional>
#include <utility>
const int ha = 1000000007;
inline void add(int &p, const int &val) {
  p += val; if(p >= ha) p -= ha;
}

const int maxn = 3005;
int R[maxn], f[maxn][maxn];
char S[maxn]; int sum[maxn];
int main() {
  int n, m; scanf("%d%d", &n, &m);
  scanf("%s", S + 1);
  for(int i = 1; i <= n; i ++) {
    sum[i] = sum[i - 1] + S[i] - '0';
    R[i] = i;
  }
  while(m --) {
    int l, r; scanf("%d%d", &l, &r);
    R[l] = std::max(R[l], r);
  }
  for(int i = 2; i <= n; i ++) R[i] = std::max(R[i], R[i - 1]);
  R[n + 1] = n;
  f[1][sum[R[1]]] = 1;
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j <= n; j ++) {
      int th = f[i][j];
      if(!th) continue;
#ifdef LOCAL
      printf("f[%d][%d] : %d\n", i, j, f[i][j]);
#endif
      int delta = sum[R[i + 1]] - sum[R[i]];
      if(j) add(f[i + 1][j + delta - 1], th);
      if(R[i] - i >= j) add(f[i + 1][j + delta], th);
    }
  }
  printf("%d\n", f[n + 1][0]);
  return 0;
}