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 <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <functional>
#include <iostream>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n,m;
ll dp[3001][3001];
string str;
int nex[3001];
int cnt[3001];

int main(void){
	scanf("%d%d",&n,&m);
	cin >> str;
	for(int i=0;i<n;i++){
		cnt[i+1]+=cnt[i];
		if(str[i]=='1')cnt[i+1]++;
	}
	memset(nex,-1,sizeof(nex));
	for(int i=0;i<m;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		l--;
		nex[l]=max(nex[l],r);
	}
	dp[0][0]=1;
	int r=-1;
	for(int i=0;i<n;i++){
		r=max(nex[i],r);
		for(int j=0;j<=i;j++){
			if(r<=i){
				if(str[i]=='0'){
					dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
				}else{
					dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%MOD;
				}
			}else{
				if(j<cnt[r]){
					dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%MOD;
				}
				if(i-j<r-cnt[r]){
					dp[i+1][j]=(dp[i+1][j]+dp[i][j])%MOD;
				}
			}
		}
	}
	printf("%lld\n",dp[n][cnt[n]]);
	return 0;
}