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 <cstdio>
#include <cstring>
#include <cassert>
typedef long long lint;
const int N=3005;
const int mod=1e9+7;
int n,q,dp[N],lim_r[N],sum0[N];

namespace utils{
	template <class T> inline void apx(T &x,const T y){
		x<y?x=y:0;
	}
	template <class T> inline void apn(T &x,const T y){
		x>y?x=y:0;
	}
	inline int nxi(FILE *fd=stdin){
		int x=0;
		char c;
		while(((c=fgetc(fd))>'9'||c<'0')&&c!='-');
		const bool f=(c=='-')&&(c=fgetc(fd));
		while(x=x*10-48+c,(c=fgetc(fd))>='0'&&c<='9');
		return f?-x:x;
	}
}
using namespace utils;

int main(){
	static char str[N];
	n=nxi(),q=nxi();
	scanf("%s",str+1);
	for(int i=1; i<=n; ++i){
		lim_r[i]=i;
		sum0[i]=sum0[i-1]+(str[i]=='0');
	}
	for(int i=1; i<=q; ++i){
		const int x=nxi(),y=nxi();
		for(int i=x; i<y; ++i){
			apx(lim_r[i],y);
		}
	}
	for(int i=1; i<=n; ++i){
		apx(lim_r[i],lim_r[i-1]);
	}
	dp[0]=1;
	for(int i=0; i<n; ++i){
		static int fp[N];
		memcpy(fp,dp,n*sizeof(int));
		memset(dp,0,n*sizeof(int));
		int r=lim_r[i+1];
		int add_0=sum0[r]-sum0[lim_r[i]];
		for(int j=0; j<=r; ++j){
			if(!fp[j]) continue;
			//print 1
			if(j+add_0<r-i){
				dp[j+add_0]=(dp[j+add_0]+fp[j])%mod;
			}
			//print 0
			if(j+add_0-1>=0){
				dp[j+add_0-1]=(dp[j+add_0-1]+fp[j])%mod;
			}
		}
	}
	printf("%d\n",dp[0]);
	return 0;
}