#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

const lint mod = 1e9 + 7;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  string s; cin >> s;
  V<> a(n);
  for (int i = 0; i < n; i++) a[i] = i + 1;
  for (int i = 0; i < m; i++) {
    int l, r; cin >> l >> r, l--;
    for (int j = l; j < r; j++) a[j] = max(a[j], r);
  }
  V<> c(n + 1);
  for (int i = 0; i < n; i++) c[i + 1] = c[i] + (s[i] == '1');
  VV<lint> dp; assign(dp, n + 1, n + 1);
  dp[1][0] = a[0] - c[a[0]] > 0;
  dp[1][1] = c[a[0]] > 0;
  for (int i = 1; i < n; i++) for (int j = 0; j < n + 1; j++) {
    if ((a[i] - i) - (c[a[i]] - j) > 0) (dp[i + 1][j] += dp[i][j]) %= mod;
    if (c[a[i]] - j > 0) (dp[i + 1][j + 1] += dp[i][j]) %= mod;
  }
  lint res = 0;
  for (int j = 0; j < n + 1; j++) (res += dp[n][j]) %= mod;
  cout << emod(res) << '\n';
}
### Prompt

Please formulate a Cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

const lint mod = 1e9 + 7;
inline lint emod(lint a, lint p = mod) { return (a % p + p) % p; }

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m; cin >> n >> m;
  string s; cin >> s;
  V<> a(n);
  for (int i = 0; i < n; i++) a[i] = i + 1;
  for (int i = 0; i < m; i++) {
    int l, r; cin >> l >> r, l--;
    for (int j = l; j < r; j++) a[j] = max(a[j], r);
  }
  V<> c(n + 1);
  for (int i = 0; i < n; i++) c[i + 1] = c[i] + (s[i] == '1');
  VV<lint> dp; assign(dp, n + 1, n + 1);
  dp[1][0] = a[0] - c[a[0]] > 0;
  dp[1][1] = c[a[0]] > 0;
  for (int i = 1; i < n; i++) for (int j = 0; j < n + 1; j++) {
    if ((a[i] - i) - (c[a[i]] - j) > 0) (dp[i + 1][j] += dp[i][j]) %= mod;
    if (c[a[i]] - j > 0) (dp[i + 1][j + 1] += dp[i][j]) %= mod;
  }
  lint res = 0;
  for (int j = 0; j < n + 1; j++) (res += dp[n][j]) %= mod;
  cout << emod(res) << '\n';
}
```