#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int mod=1e9+7;
void add(int &x,int y){
	x+=y;
	if(x>=mod) x-=mod;
}
int N,M,l[3000],r[3000];
int mn[3001],mx[3001];
int dp[3001][3001];
string s,so;
int main(){
	cin>>N>>M;
	cin>>s;
	so=s;
	rep(i,M) cin>>l[i]>>r[i],l[i]--;
	rep(t,2){
		s=so;
		rep(i,M){
			int c[2]={};
			for(int j=l[i];j<r[i];j++) c[s[j]-'0']++;
			for(int j=l[i];j<l[i]+c[t];j++) s[j]='0'+t;
			for(int j=l[i]+c[t];j<r[i];j++) s[j]='0'+(1-t);
		}
		if(t==0){
			rep(i,N) mn[i+1]=mn[i]+(s[i]=='1');
		}
		if(t==1){
			rep(i,N) mx[i+1]=mx[i]+(s[i]=='1');
		}
	}
	dp[0][0]=1;
	rep(i,N) rep(j,i+1) if(dp[i][j]){
		rep(k,2){
			int ni=i+1;
			int nj=j+k;
			if(mn[ni]<=nj&&nj<=mx[ni]) add(dp[ni][nj],dp[i][j]);
		}
	}
	cout<<dp[N][mn[N]]<<endl;
}

### 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 rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
int mod=1e9+7;
void add(int &x,int y){
	x+=y;
	if(x>=mod) x-=mod;
}
int N,M,l[3000],r[3000];
int mn[3001],mx[3001];
int dp[3001][3001];
string s,so;
int main(){
	cin>>N>>M;
	cin>>s;
	so=s;
	rep(i,M) cin>>l[i]>>r[i],l[i]--;
	rep(t,2){
		s=so;
		rep(i,M){
			int c[2]={};
			for(int j=l[i];j<r[i];j++) c[s[j]-'0']++;
			for(int j=l[i];j<l[i]+c[t];j++) s[j]='0'+t;
			for(int j=l[i]+c[t];j<r[i];j++) s[j]='0'+(1-t);
		}
		if(t==0){
			rep(i,N) mn[i+1]=mn[i]+(s[i]=='1');
		}
		if(t==1){
			rep(i,N) mx[i+1]=mx[i]+(s[i]=='1');
		}
	}
	dp[0][0]=1;
	rep(i,N) rep(j,i+1) if(dp[i][j]){
		rep(k,2){
			int ni=i+1;
			int nj=j+k;
			if(mn[ni]<=nj&&nj<=mx[ni]) add(dp[ni][nj],dp[i][j]);
		}
	}
	cout<<dp[N][mn[N]]<<endl;
}

```