#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int N = 3005;
const i64 MOD = 1000000007;

int v[N], st[N], dr[N];
i64 dp[N][N];

vector<pii> ivs;
string str;
int n, m, one;

int main() {
#ifdef HOME
	freopen("arc65d.in", "r", stdin);
	freopen("arc65d.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> str;
	ivs.resize(m);
	for (auto &i: ivs)
		cin >> i.x >> i.y;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		st[v[i]] = i;

	memset(v, 0x00, sizeof v);
	one = 0;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return !x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		dr[v[i]] = i;

	for (int i = 0; i <= n; ++i)
		dp[i][0] = 1;

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= one; ++j) {
			dp[i][j]+= dp[i - 1][j];

			if (st[j] <= i && i <= dr[j]) 
				dp[i][j]+= dp[i - 1][j - 1];

			if (dp[i][j] >= MOD)
				dp[i][j]-= MOD; }

	cout << dp[n][one] % MOD << endl;

	return 0; }

### Prompt

Create a solution in CPP for 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>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<int, int>;

const int N = 3005;
const i64 MOD = 1000000007;

int v[N], st[N], dr[N];
i64 dp[N][N];

vector<pii> ivs;
string str;
int n, m, one;

int main() {
#ifdef HOME
	freopen("arc65d.in", "r", stdin);
	freopen("arc65d.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	cin >> str;
	ivs.resize(m);
	for (auto &i: ivs)
		cin >> i.x >> i.y;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		st[v[i]] = i;

	memset(v, 0x00, sizeof v);
	one = 0;

	for (int i = 0; i < n; ++i) if (str[i] == '1')
		v[i + 1] = ++one;

	for (int i = 0; i < m; ++i)
		stable_partition(v + ivs[i].x, v + ivs[i].y + 1, [&](int x) { return !x; });
	for (int i = 1; i <= n; ++i) if (v[i])
		dr[v[i]] = i;

	for (int i = 0; i <= n; ++i)
		dp[i][0] = 1;

	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= one; ++j) {
			dp[i][j]+= dp[i - 1][j];

			if (st[j] <= i && i <= dr[j]) 
				dp[i][j]+= dp[i - 1][j - 1];

			if (dp[i][j] >= MOD)
				dp[i][j]-= MOD; }

	cout << dp[n][one] % MOD << endl;

	return 0; }

```