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;

typedef long double ld;
typedef long long ll;

const int M = 3030;
const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int udd(int &x, int y) {
  return x = add(x, y);
}

int n, m;
int l[M], r[M];
int up[M], down[M];
int d[M][M];
string s;

void read() {
  cin >> n >> m >> s;
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    --l;
    ::l[i] = l;
    ::r[i] = r;
  }
}

void calc(string s, function<bool(char, char)> cmp, int *to) {
  for (int i = 0; i < m; ++i)
    sort(s.begin() + l[i], s.begin() + r[i], cmp);
  for (int i = 0; i < n; ++i)
    to[i + 1] = to[i] + (s[i] - '0');
}

void kill() {
  calc(s, less<char>(), down);
  calc(s, greater<char>(), up);
  d[0][0] = 1;
  int A = down[n];
  int B = n - A;
  for (int i = 0; i <= A; ++i)
    for (int j = 0; j <= B; ++j) {
      int k = i + j;
      if (down[k] <= i && i <= up[k]) {
        int cur = d[i][j];
        udd(d[i + 1][j], cur);
        udd(d[i][j + 1], cur);
      }
    }

  cout << d[A][B] << endl;
}

int main() {
#ifdef LOCAL
  assert(freopen("f.in", "r", stdin));
#endif

  ios_base::sync_with_stdio(false);

  read();
  kill();
}