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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define int long long
using namespace std;

int n, m;
string s;

int cnt[3005];
int mx[3005], mn[3005];
int dp[3005][3005];
signed main()
{
	cin>>n>>m>>s;
	for(int i=1; i<=n; i++)
	{
		cnt[i]=cnt[i-1]+(s[i-1]=='1');
		mx[i]=cnt[i], mn[i]=cnt[i];
	}
	for(int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;

		int lol=mn[r]-mn[l-1], lel=mx[r]-mx[l-1];

		for(int j=l; j<=r; j++)
		{
			mn[j]=min(mn[j], mn[l-1]+max(0ll, lol-(r-j)));
			mx[j]=max(mx[j], mx[l-1]+min(j-l+1, lel));
		}
	}
	// for(int i=1; i<=n; i++)
	// {
	// 	cout<<mx[i]<<" "<<mn[i]<<endl;
	// }
	dp[0][0]=1;
	for(int i=1; i<=n; i++)
	{
		for(int j=mn[i]; j<=mx[i]; j++)
		{
			if(j>0)
			{
				dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
			}
			else
			{
				dp[i][j]=dp[i-1][j];
			}
			dp[i][j]%=1000000007;
		}
	}
	cout<<dp[n][cnt[n]];
}