#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3010,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int n,m,top,l[N],r[N],cnt[N];
char s[N];
int dp[N][N],C[N][N];//dp[i][j]表示填完了前l[i+1]-1个，手里剩下j个1的方案数
int calc(){
	for (int i=0;i<=top;i++)
	for (int j=0;j<=n;j++)
		dp[i][j]=0;
	dp[0][0]=1;l[0]=l[1];r[0]=l[1]-1;
	for (int i=0;i<top;i++){
		int len=l[i+1]-l[i],one=cnt[r[i+1]]-cnt[r[i]];
		for (int j=0;j<=n;j++){
			int v=dp[i][j],zero=r[i]-l[i]+1-j;
			for (int k=max(0,len-zero);k<=j&&k<=len;k++)//考虑一下填多少个1
				dp[i+1][j-k+one]=inc(dp[i+1][j-k+one],mul(v,C[len][k]));
		}
	}
	l[0]=r[0]=0;
	int ans=0;
	for (int j=0;j<=n;j++) ans=inc(ans,mul(dp[top][j],C[r[top]-l[top]+1][j]));
	return ans;
}
int main()
{
	scanf("%d%d%s",&n,&m,s+1);
	for (int i=0;i<=n;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=inc(C[i-1][j-1],C[i-1][j]);
	}
	for (int i=1;i<=n;i++) cnt[i]=cnt[i-1]+s[i]-'0';
	int ans=1;
	for (int i=1;i<=m;i++){
		int L,R;
		scanf("%d%d",&L,&R);
		if (top&&L>r[top]) ans=mul(ans,calc()),top=0;
		if (R>r[top]) top++,l[top]=L,r[top]=R;
	}
	ans=mul(ans,calc());
	printf("%d\n",ans);
	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<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=3010,p=1e9+7;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int n,m,top,l[N],r[N],cnt[N];
char s[N];
int dp[N][N],C[N][N];//dp[i][j]表示填完了前l[i+1]-1个，手里剩下j个1的方案数
int calc(){
	for (int i=0;i<=top;i++)
	for (int j=0;j<=n;j++)
		dp[i][j]=0;
	dp[0][0]=1;l[0]=l[1];r[0]=l[1]-1;
	for (int i=0;i<top;i++){
		int len=l[i+1]-l[i],one=cnt[r[i+1]]-cnt[r[i]];
		for (int j=0;j<=n;j++){
			int v=dp[i][j],zero=r[i]-l[i]+1-j;
			for (int k=max(0,len-zero);k<=j&&k<=len;k++)//考虑一下填多少个1
				dp[i+1][j-k+one]=inc(dp[i+1][j-k+one],mul(v,C[len][k]));
		}
	}
	l[0]=r[0]=0;
	int ans=0;
	for (int j=0;j<=n;j++) ans=inc(ans,mul(dp[top][j],C[r[top]-l[top]+1][j]));
	return ans;
}
int main()
{
	scanf("%d%d%s",&n,&m,s+1);
	for (int i=0;i<=n;i++){
		C[i][0]=1;
		for (int j=1;j<=i;j++) C[i][j]=inc(C[i-1][j-1],C[i-1][j]);
	}
	for (int i=1;i<=n;i++) cnt[i]=cnt[i-1]+s[i]-'0';
	int ans=1;
	for (int i=1;i<=m;i++){
		int L,R;
		scanf("%d%d",&L,&R);
		if (top&&L>r[top]) ans=mul(ans,calc()),top=0;
		if (R>r[top]) top++,l[top]=L,r[top]=R;
	}
	ans=mul(ans,calc());
	printf("%d\n",ans);
	return 0;
}
```