#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 3000;
const int MaxM = 3000;
const int M = 1000000007;

int n, m;
char s[MaxN + 3];

int sum[MaxN + 1];

int pos[MaxN + 1];

int f[MaxN + 2][MaxN + 1];

inline void add(int i, int j, int d)
{
	f[i][j] = (f[i][j] + d) % M;
}

int main()
{
	cin >> n >> m;
	cin >> s + 1;

	for (int i = 1; i <= n; ++i)
		sum[i] = s[i] - '0';
	for (int i = 2; i <= n + 1; ++i)
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n + 1; ++i)
		pos[i] = i;
	for (int i = 1; i <= m; ++i)
	{
		int l = getint();
		pos[l] = max(pos[l], getint());
	}

	for (int i = 1; i <= n; ++i)
		pos[i] = max(pos[i], pos[i - 1]);

	f[1][sum[pos[1]]] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
		{
			int cur = f[i][j];
			if (cur == 0)
				continue;

			int l = sum[pos[i + 1]] - sum[pos[i]];
			int k = pos[i] - i + 1 - j;
			if (k > 0)
				add(i + 1, j + l - 0, cur);
			if (j > 0)
				add(i + 1, j + l - 1, cur);
		}

	cout << f[n + 1][0] << endl;

	return 0;
}
### Prompt

Please create a solution in cpp to the following 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

### Response

```cpp
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 3000;
const int MaxM = 3000;
const int M = 1000000007;

int n, m;
char s[MaxN + 3];

int sum[MaxN + 1];

int pos[MaxN + 1];

int f[MaxN + 2][MaxN + 1];

inline void add(int i, int j, int d)
{
	f[i][j] = (f[i][j] + d) % M;
}

int main()
{
	cin >> n >> m;
	cin >> s + 1;

	for (int i = 1; i <= n; ++i)
		sum[i] = s[i] - '0';
	for (int i = 2; i <= n + 1; ++i)
		sum[i] += sum[i - 1];

	for (int i = 1; i <= n + 1; ++i)
		pos[i] = i;
	for (int i = 1; i <= m; ++i)
	{
		int l = getint();
		pos[l] = max(pos[l], getint());
	}

	for (int i = 1; i <= n; ++i)
		pos[i] = max(pos[i], pos[i - 1]);

	f[1][sum[pos[1]]] = 1;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
		{
			int cur = f[i][j];
			if (cur == 0)
				continue;

			int l = sum[pos[i + 1]] - sum[pos[i]];
			int k = pos[i] - i + 1 - j;
			if (k > 0)
				add(i + 1, j + l - 0, cur);
			if (j > 0)
				add(i + 1, j + l - 1, cur);
		}

	cout << f[n + 1][0] << endl;

	return 0;
}
```