#include<bits/stdc++.h>
using namespace std;
#define N 3333
#define mod 1000000007

int n,m,a[N],r[N],f[N][N];
char s[N];

void pls(int &x,int y){x=(x+y)%mod;}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();m=read();scanf(" %s",s+1);
	for (int i=1;i<=n;i++)
		a[i]=a[i-1]+(s[i]=='1');
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		r[x]=max(r[x],y);
	}
	for (int i=1;i<=n;i++)
		r[i]=max(max(r[i-1],r[i]),i);
	f[0][0]=1;
	for (int i=0;i<n;i++)
		for (int j=0;j<=n;j++){
			if (j+a[r[i+1]]-a[r[i]]) pls(f[i+1][j+a[r[i+1]]-a[r[i]]-1],f[i][j]);
			if (r[i+1]-i-j-a[r[i+1]]+a[r[i]]) pls(f[i+1][j+a[r[i+1]]-a[r[i]]],f[i][j]);
		}
	printf("%d\n",(f[n][0]+mod)%mod);
	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;
#define N 3333
#define mod 1000000007

int n,m,a[N],r[N],f[N][N];
char s[N];

void pls(int &x,int y){x=(x+y)%mod;}

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();m=read();scanf(" %s",s+1);
	for (int i=1;i<=n;i++)
		a[i]=a[i-1]+(s[i]=='1');
	for (int i=1;i<=m;i++){
		int x=read(),y=read();
		r[x]=max(r[x],y);
	}
	for (int i=1;i<=n;i++)
		r[i]=max(max(r[i-1],r[i]),i);
	f[0][0]=1;
	for (int i=0;i<n;i++)
		for (int j=0;j<=n;j++){
			if (j+a[r[i+1]]-a[r[i]]) pls(f[i+1][j+a[r[i+1]]-a[r[i]]-1],f[i][j]);
			if (r[i+1]-i-j-a[r[i+1]]+a[r[i]]) pls(f[i+1][j+a[r[i+1]]-a[r[i]]],f[i][j]);
		}
	printf("%d\n",(f[n][0]+mod)%mod);
	return 0;
}
```