#pragma GCC optimize("unroll-loops,Ofast")
#pragma GCC target("avx,sse,sse2,ssse3,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 3030, mod = 1e9 + 7;
int n, m, jump[maxn], nxt[2][maxn][maxn], dp[maxn][maxn][2];
string s;
void add(int &a, int b) {
	a += b;
	if(a >= mod) a -= mod;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> s;
	for(int i = 0; i < n; i++) jump[i] = i;
	for(int l, r, i = 0; i < m; i++) {
		cin >> l >> r; --l, --r;
		jump[l] = max(jump[l], r);
	}
	for(int i = 1; i < n; i++) jump[i] = max(jump[i], jump[i-1]);
	memset(nxt, 0x3f, sizeof nxt);
	for(int c = 0; c < 2; c++)
	for(int i = n; i--;) {
		if(s[i] == char('0'+c)) nxt[c][i][0] = i;
		else nxt[c][i][0] = nxt[c][i+1][0];
		for(int j = 1; j < n; j++) {
			nxt[c][i][j] = nxt[c][i+1][j-(s[i]==char('0'+c))];
		}
	}
	dp[0][0][0] = 1;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			for(int p = 0; p < 2; p++) {
				int cur = s[i]-'0';
				int ni = i+1;
				int nj = j;
				if(cur == p && nj)
					nj--, cur ^= 1;
				add(dp[ni][nj][p], dp[i][j][p]);
				if(nxt[cur^1][i][j] <= jump[i])
					add(dp[ni][nj+1][cur^1], dp[i][j][p]);
			}
		}
	}
	add(dp[n][0][0], dp[n][0][1]);
	cout << dp[n][0][0];
}

### Prompt

Your task is to create 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
#pragma GCC optimize("unroll-loops,Ofast")
#pragma GCC target("avx,sse,sse2,ssse3,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 3030, mod = 1e9 + 7;
int n, m, jump[maxn], nxt[2][maxn][maxn], dp[maxn][maxn][2];
string s;
void add(int &a, int b) {
	a += b;
	if(a >= mod) a -= mod;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> s;
	for(int i = 0; i < n; i++) jump[i] = i;
	for(int l, r, i = 0; i < m; i++) {
		cin >> l >> r; --l, --r;
		jump[l] = max(jump[l], r);
	}
	for(int i = 1; i < n; i++) jump[i] = max(jump[i], jump[i-1]);
	memset(nxt, 0x3f, sizeof nxt);
	for(int c = 0; c < 2; c++)
	for(int i = n; i--;) {
		if(s[i] == char('0'+c)) nxt[c][i][0] = i;
		else nxt[c][i][0] = nxt[c][i+1][0];
		for(int j = 1; j < n; j++) {
			nxt[c][i][j] = nxt[c][i+1][j-(s[i]==char('0'+c))];
		}
	}
	dp[0][0][0] = 1;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			for(int p = 0; p < 2; p++) {
				int cur = s[i]-'0';
				int ni = i+1;
				int nj = j;
				if(cur == p && nj)
					nj--, cur ^= 1;
				add(dp[ni][nj][p], dp[i][j][p]);
				if(nxt[cur^1][i][j] <= jump[i])
					add(dp[ni][nj+1][cur^1], dp[i][j][p]);
			}
		}
	}
	add(dp[n][0][0], dp[n][0][1]);
	cout << dp[n][0][0];
}

```