#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,to=b;i<to;++i)
#define MOD 1000000007
using namespace std;
typedef long long ll;


int cc[3005][3005];

int comb(int n, int k){
	return cc[n][k];
}

char s[4096];
int n,m;
vector<pair<int,int> > w;
int sp[4096];
map<int,int> z;
int dp[3005][3005];

int f(int k, int q){
	if(dp[k][q]>=0)return dp[k][q];
	int r;
	if(k==w.size())r=1;
	else {
		int s=w[k].fst;
		int e=w[k].snd;
		int m0;
		if(k>0)m0=max(s,w[k-1].snd);
		else m0=s;
		int m1;
		if(k<w.size()-1)m1=min(e,w[k+1].fst);
		else m1=e;
		int n1=sp[e]-sp[m0]+q;
		int n0=e-s-n1;
		r=0;
		fore(j,0,min(e-m1,n1)+1){
			int jj=n1-j;
			r+=(1LL*comb(m1-s,jj)*f(k+1,j))%MOD;
			r%=MOD;
		}
	}
	return dp[k][q]=r;
}


int main(){
	memset(cc,0,sizeof(cc));
	fore(i,1,3005){
		cc[i][0]=cc[i][i]=1;
		fore(j,1,i){
			cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%MOD;
		}
	}
	scanf("%d%d%s",&n,&m,s);
	sp[0]=0;
	fore(i,1,n+1){
		sp[i]=sp[i-1]+s[i-1]-'0';
	}
	fore(i,0,m){
		int x,y;
		scanf("%d%d",&x,&y);x--;
		z[x]=max(z[x],y);
	}
	int k=-1;
	for(map<int,int>::iterator it=z.begin();it!=z.end();++it){
		int x=it->fst,y=it->snd;
		if(y<=k)continue;
		k=max(k,y);
		w.pb(mp(x,y));
	}
	memset(dp,-1,sizeof(dp));
	printf("%d\n",f(0,0));
	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 pb push_back
#define mp make_pair
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,to=b;i<to;++i)
#define MOD 1000000007
using namespace std;
typedef long long ll;


int cc[3005][3005];

int comb(int n, int k){
	return cc[n][k];
}

char s[4096];
int n,m;
vector<pair<int,int> > w;
int sp[4096];
map<int,int> z;
int dp[3005][3005];

int f(int k, int q){
	if(dp[k][q]>=0)return dp[k][q];
	int r;
	if(k==w.size())r=1;
	else {
		int s=w[k].fst;
		int e=w[k].snd;
		int m0;
		if(k>0)m0=max(s,w[k-1].snd);
		else m0=s;
		int m1;
		if(k<w.size()-1)m1=min(e,w[k+1].fst);
		else m1=e;
		int n1=sp[e]-sp[m0]+q;
		int n0=e-s-n1;
		r=0;
		fore(j,0,min(e-m1,n1)+1){
			int jj=n1-j;
			r+=(1LL*comb(m1-s,jj)*f(k+1,j))%MOD;
			r%=MOD;
		}
	}
	return dp[k][q]=r;
}


int main(){
	memset(cc,0,sizeof(cc));
	fore(i,1,3005){
		cc[i][0]=cc[i][i]=1;
		fore(j,1,i){
			cc[i][j]=(cc[i-1][j-1]+cc[i-1][j])%MOD;
		}
	}
	scanf("%d%d%s",&n,&m,s);
	sp[0]=0;
	fore(i,1,n+1){
		sp[i]=sp[i-1]+s[i-1]-'0';
	}
	fore(i,0,m){
		int x,y;
		scanf("%d%d",&x,&y);x--;
		z[x]=max(z[x],y);
	}
	int k=-1;
	for(map<int,int>::iterator it=z.begin();it!=z.end();++it){
		int x=it->fst,y=it->snd;
		if(y<=k)continue;
		k=max(k,y);
		w.pb(mp(x,y));
	}
	memset(dp,-1,sizeof(dp));
	printf("%d\n",f(0,0));
	return 0;
}
```