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 <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MOD = 1000000007;

int main(){
	int N, M;
	static long long dp[3001][3001];
	while(cin >> N >> M){
		string S; cin >> S;
		vector<int> upperNum(N, 0);
		vector<int> right(N, 0);
		for(int i=0;i<N;i++) right[i] = i;
		for(int i=0;i<M;i++){
			int l, r; cin >> l >> r;
			--l; --r;
			right[l] = max(right[l], r);
		}
		for(int i=1;i<N;i++) right[i] = max(right[i], right[i-1]);
		upperNum[0] = (S[0] == '1');
		for(int i=1;i<N;i++){
			upperNum[i] = upperNum[i-1] + (S[i] == '1');
		}
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		int lower = 0;
		for(int i=0;i<N;i++){
			if(lower + right[i] - i + 1 == upperNum[right[i]]) ++lower;
			int upper = upperNum[right[i]];
			for(int j=0;j<N;j++){
				for(int k=0;k<2;k++){
					if(lower <= j+k && j+k <= upper) dp[i+1][j+k] = (dp[i][j]+dp[i+1][j+k])%MOD;
				}
			}
		}
		cout << dp[N][upperNum[N-1]] << endl;
	}
}