#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=3000,mod=1000000007;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n,nxt[N+9];

void into(){
  int m;
  scanf("%d%d",&n,&m);
  scanf("%s",s+1);
  for (int i=1;i<=m;++i){
	int l,r;
	scanf("%d%d",&l,&r);
	nxt[l]=max(nxt[l],r);
  }
}

int a[N+9];

void Get_a(){
  for (int i=1;i<=n;++i) a[i]=s[i]-'0'+a[i-1];
  a[n+1]=a[n];
}

void Get_nxt(){
  for (int i=1;i<=n+1;++i){
	if (!nxt[i]) nxt[i]=i;
	nxt[i]=max(nxt[i],nxt[i-1]);
  }
}

int dp[N+9][N+9];

void Get_dp(){
  dp[1][a[nxt[1]]]=1;
  for (int i=1;i<=n;++i)
	for (int j=0;j<=n;++j){
	  if (!dp[i][j]) continue;
	  int l=nxt[i],r=nxt[i+1],c0=nxt[i]-i+1-j,c1=j;
	  if (c1) sadd(dp[i+1][j+a[r]-a[l]-1],dp[i][j]);
	  if (c0) sadd(dp[i+1][j+a[r]-a[l]],dp[i][j]);
	}
}

void work(){
  Get_a();
  Get_nxt();
  Get_dp();
}

void outo(){
  printf("%d\n",dp[n+1][0]);
}

int main(){
  into();
  work();
  outo();
  return 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
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N=3000,mod=1000000007;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n,nxt[N+9];

void into(){
  int m;
  scanf("%d%d",&n,&m);
  scanf("%s",s+1);
  for (int i=1;i<=m;++i){
	int l,r;
	scanf("%d%d",&l,&r);
	nxt[l]=max(nxt[l],r);
  }
}

int a[N+9];

void Get_a(){
  for (int i=1;i<=n;++i) a[i]=s[i]-'0'+a[i-1];
  a[n+1]=a[n];
}

void Get_nxt(){
  for (int i=1;i<=n+1;++i){
	if (!nxt[i]) nxt[i]=i;
	nxt[i]=max(nxt[i],nxt[i-1]);
  }
}

int dp[N+9][N+9];

void Get_dp(){
  dp[1][a[nxt[1]]]=1;
  for (int i=1;i<=n;++i)
	for (int j=0;j<=n;++j){
	  if (!dp[i][j]) continue;
	  int l=nxt[i],r=nxt[i+1],c0=nxt[i]-i+1-j,c1=j;
	  if (c1) sadd(dp[i+1][j+a[r]-a[l]-1],dp[i][j]);
	  if (c0) sadd(dp[i+1][j+a[r]-a[l]],dp[i][j]);
	}
}

void work(){
  Get_a();
  Get_nxt();
  Get_dp();
}

void outo(){
  printf("%d\n",dp[n+1][0]);
}

int main(){
  into();
  work();
  outo();
  return 0;
}
```