#include<iostream>
#include<cstdio>
#define MN 3000
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,s[MN+5],f[MN+5],g[MN+5],l[MN+5],r[MN+5],p[MN+5],inv[MN+5];
char st[MN+5];
void Move(int s)
{
	for(int i=n;i>=s;--i) f[i]=f[i-s];
	for(int i=0;i<s;++i) f[i]=0;
}
inline int C(int n,int m){return 1LL*p[n]*inv[m]%mod*inv[n-m]%mod;} 
int main()
{
	n=read();m=read();scanf("%s",st+1);p[0]=p[1]=inv[0]=inv[1]=f[0]=1;
	for(int i=1;i<=n;++i) s[i]=s[i-1]+(st[i]=='1');
	for(int i=2;i<=n;++i) p[i]=1LL*p[i-1]*i%mod,inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;++i) inv[i]=1LL*inv[i-1]*inv[i]%mod;n=0;
	for(int i=1;i<=m;++i) l[i]=read(),n=max(n,r[i]=read());l[m+1]=n+1;
	for(int i=1,mr=l[1]-1;i<=m;++i)
	{
		if(r[i]>mr) Move(s[r[i]]-s[mr]),mr=r[i];
		if(l[i+1]>l[i])
		{
			int len=min(l[i+1]-1,mr)-l[i]+1;
			for(int j=0;j<=n;++j) if(f[j])
			{
				for(int k=0;k<=j&&k<=len;++k) if(mr-l[i]+1-j>=len-k)
					g[j-k]=(g[j-k]+1LL*f[j]*C(len,k))%mod;	
			}
			for(int j=0;j<=n;++j) f[j]=g[j],g[j]=0;
			mr=max(mr,l[i+1]-1);
		}
	}
	printf("%d\n",f[0]);
	return 0;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

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<iostream>
#include<cstdio>
#define MN 3000
#define mod 1000000007
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,s[MN+5],f[MN+5],g[MN+5],l[MN+5],r[MN+5],p[MN+5],inv[MN+5];
char st[MN+5];
void Move(int s)
{
	for(int i=n;i>=s;--i) f[i]=f[i-s];
	for(int i=0;i<s;++i) f[i]=0;
}
inline int C(int n,int m){return 1LL*p[n]*inv[m]%mod*inv[n-m]%mod;} 
int main()
{
	n=read();m=read();scanf("%s",st+1);p[0]=p[1]=inv[0]=inv[1]=f[0]=1;
	for(int i=1;i<=n;++i) s[i]=s[i-1]+(st[i]=='1');
	for(int i=2;i<=n;++i) p[i]=1LL*p[i-1]*i%mod,inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=n;++i) inv[i]=1LL*inv[i-1]*inv[i]%mod;n=0;
	for(int i=1;i<=m;++i) l[i]=read(),n=max(n,r[i]=read());l[m+1]=n+1;
	for(int i=1,mr=l[1]-1;i<=m;++i)
	{
		if(r[i]>mr) Move(s[r[i]]-s[mr]),mr=r[i];
		if(l[i+1]>l[i])
		{
			int len=min(l[i+1]-1,mr)-l[i]+1;
			for(int j=0;j<=n;++j) if(f[j])
			{
				for(int k=0;k<=j&&k<=len;++k) if(mr-l[i]+1-j>=len-k)
					g[j-k]=(g[j-k]+1LL*f[j]*C(len,k))%mod;	
			}
			for(int j=0;j<=n;++j) f[j]=g[j],g[j]=0;
			mr=max(mr,l[i+1]-1);
		}
	}
	printf("%d\n",f[0]);
	return 0;
}
```