#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define C(n,m) ((LL)fac[n]*ifac[m]%mo*ifac[(n)-(m)]%mo)

const int maxn=3010;
const int mo=1e9+7;

int n,m,m0,l[maxn],r[maxn];
int fac[6010],ifac[6010],dp[maxn][maxn];
bool s[maxn];

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,j;
	char c;

	fac[0]=1;
	for (i=1;i<=6000;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	ifac[6000]=power(fac[6000],mo-2);
	for (i=6000;i>=1;i--)
		ifac[i-1]=(LL)ifac[i]*i%mo;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		c=getchar();
		while (c!='0'&&c!='1') c=getchar();
		s[i]=c=='1';
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		if (r[i]>r[m0])
			m0++,l[m0]=l[i],r[m0]=r[i];
	}
	m=m0;
	l[m+1]=r[m+1]=2333333;

	int p=1;
	dp[1][0]=1;
	for (i=1;i<=m;i++)
	{
//		printf("i=%d\n",i);
		int cnt=0;
		p=max(p,l[i]);
		while (p<=r[i]) cnt+=s[p++];
		for (j=0;j<=n;j++) if (dp[i][j])
		{
			int R=max(0,r[i]-l[i+1]+1);
			int L=r[i]-l[i]+1-R;
			for (int k=max(0,cnt+j-L);k<=R&&k<=cnt+j;k++)
				(dp[i+1][k]+=(LL)dp[i][j]*C(L,cnt+j-k)%mo)%=mo;
		}
//		puts(""); puts("");
	}
	printf("%d\n",dp[m+1][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<bits/stdc++.h>
using namespace std;
#define LL long long
#define C(n,m) ((LL)fac[n]*ifac[m]%mo*ifac[(n)-(m)]%mo)

const int maxn=3010;
const int mo=1e9+7;

int n,m,m0,l[maxn],r[maxn];
int fac[6010],ifac[6010],dp[maxn][maxn];
bool s[maxn];

int power(int x,int k)
{
	int res=1;
	while (k)
	{
		if (k&1) res=(LL)res*x%mo;
		x=(LL)x*x%mo;
		k>>=1;
	}
	return res;
}

int main()
{
#ifdef h10
	freopen("F.in","r",stdin);
	freopen("F.out","w",stdout);
#endif
	int i,j;
	char c;

	fac[0]=1;
	for (i=1;i<=6000;i++)
		fac[i]=(LL)fac[i-1]*i%mo;
	ifac[6000]=power(fac[6000],mo-2);
	for (i=6000;i>=1;i--)
		ifac[i-1]=(LL)ifac[i]*i%mo;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		c=getchar();
		while (c!='0'&&c!='1') c=getchar();
		s[i]=c=='1';
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		if (r[i]>r[m0])
			m0++,l[m0]=l[i],r[m0]=r[i];
	}
	m=m0;
	l[m+1]=r[m+1]=2333333;

	int p=1;
	dp[1][0]=1;
	for (i=1;i<=m;i++)
	{
//		printf("i=%d\n",i);
		int cnt=0;
		p=max(p,l[i]);
		while (p<=r[i]) cnt+=s[p++];
		for (j=0;j<=n;j++) if (dp[i][j])
		{
			int R=max(0,r[i]-l[i+1]+1);
			int L=r[i]-l[i]+1-R;
			for (int k=max(0,cnt+j-L);k<=R&&k<=cnt+j;k++)
				(dp[i+1][k]+=(LL)dp[i][j]*C(L,cnt+j-k)%mo)%=mo;
		}
//		puts(""); puts("");
	}
	printf("%d\n",dp[m+1][0]);
}

```