#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int N, M;
string S;
vector<int> L, R, T, U;
int memo[3010][3010];
bool visited[3010][3010];
long long f(int p, int q) {
	if (p == N+1) return 1;
	if (visited[p][q]) return memo[p][q];
	visited[p][q] = true;
	long long rr = 0;
	int qq = T[U[p]] - T[U[p-1]] + q;
	int x = U[p]-p+1;
	if (qq < x) { // 0
		rr += f(p+1, qq);
	}
	if (qq > 0) { // 1
		rr += f(p+1, qq-1);
	}
	return memo[p][q] = rr % mod;
}
int main() {
	cin >> N >> M >> S;
	L.resize(M);
	R.resize(M);
	for (int i = 0; i < M; ++ i) {
		cin >> L[i] >> R[i];
	}
	T.resize(N+1, -1);
	U.resize(N+1, 0);
	for (int i = 0; i < N; ++ i) {
		U[i+1] = i+1;
		T[i+1] = T[i] + (S[i] == '1' ? 1 : 0);
	}
	for (int i = 0; i < M; ++ i) {
		U[L[i]] = max(U[L[i]], R[i]);
	}
	for (int i = 0; i < N; ++ i) {
		U[i+1] = max(U[i+1], U[i]);
	}
	cout << f(1, 0) << endl;
}

### Prompt

Generate 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;
const int mod = 1000000007;
int N, M;
string S;
vector<int> L, R, T, U;
int memo[3010][3010];
bool visited[3010][3010];
long long f(int p, int q) {
	if (p == N+1) return 1;
	if (visited[p][q]) return memo[p][q];
	visited[p][q] = true;
	long long rr = 0;
	int qq = T[U[p]] - T[U[p-1]] + q;
	int x = U[p]-p+1;
	if (qq < x) { // 0
		rr += f(p+1, qq);
	}
	if (qq > 0) { // 1
		rr += f(p+1, qq-1);
	}
	return memo[p][q] = rr % mod;
}
int main() {
	cin >> N >> M >> S;
	L.resize(M);
	R.resize(M);
	for (int i = 0; i < M; ++ i) {
		cin >> L[i] >> R[i];
	}
	T.resize(N+1, -1);
	U.resize(N+1, 0);
	for (int i = 0; i < N; ++ i) {
		U[i+1] = i+1;
		T[i+1] = T[i] + (S[i] == '1' ? 1 : 0);
	}
	for (int i = 0; i < M; ++ i) {
		U[L[i]] = max(U[L[i]], R[i]);
	}
	for (int i = 0; i < N; ++ i) {
		U[i+1] = max(U[i+1], U[i]);
	}
	cout << f(1, 0) << endl;
}

```