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<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<bitset>
#include<map>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef long long LL;
typedef double db;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 3005;
const int mo = 1e+9+7;

int n,m;
int a[N],R[N];
int pre[N],ps[N];
int f[N][N];

int add(int x,int y){return x+y>=mo?x+y-mo:x+y;}

int main(){
	n=get();m=get();
	fo(i,1,n){
		char ch;
		while(ch=getchar(),ch<'0'||ch>'1');
		a[i]=ch-'0';
	}
	fo(i,1,m){
		int l=get(),r=get();
		R[l]=max(R[l],r);
	}
	fo(i,1,n){
		if (R[i]>pre[i-1])pre[i]=R[i];
		else R[i]=0,pre[i]=pre[i-1];
	}
	fo(i,1,n)ps[i]=ps[i-1]+a[i];
	f[0][0]=1;
	fo(i,0,n-1){
		int cnt,ad;
		if (!R[i+1]&&pre[i+1]<i+1)cnt=1,ad=a[i+1];
		if (!R[i+1]&&pre[i+1]>=i+1)cnt=pre[i]-i,ad=0;
		if (R[i+1])cnt=R[i+1]-i,ad=ps[R[i+1]]-ps[max(i,pre[i])];
		fo(j,0,n){
			if (j+ad)f[i+1][j+ad-1]=add(f[i+1][j+ad-1],f[i][j]);
			if (cnt-(j+ad))f[i+1][j+ad]=add(f[i+1][j+ad],f[i][j]);
		}
	}
	printf("%d\n",f[n][0]);
	return 0;
}