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 JAVA):

Solution:
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main {
	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	final long MODULO = (long) (1e9 + 7);
	int n;
	int m;
	int[] c;
	int[] l;
	int[] r;

	void run() {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		int[] s = new int[n];
		char[] S = sc.next().toCharArray();
		l = new int[m];
		r = new int[n];
		for (int i = 0; i < n; ++i) {
			r[i] = i;
		}
		for (int i = 0; i < n; ++i) {
			s[i] = (S[i] == '0' ? 0 : 1);
		}
		for (int i = 0; i < m; ++i) {
			l[i] = sc.nextInt();
			--l[i];
			r[l[i]] = Math.max(r[l[i]], sc.nextInt() - 1);
		}
		for (int i = 1; i < n; ++i) {
			r[i] = Math.max(r[i - 1], r[i]);
		}
		c = new int[n];
		for (int i = 0; i < n; ++i) {
			c[i] = (i > 0 ? c[i - 1] : 0) + s[i];
		}
		memo = new long[n][n];
		for (int i = 0; i < memo.length; ++i) {
			for (int j = 0; j < memo[i].length; ++j) {
				memo[i][j] = -1;
			}
		}
		System.out.println(f(0, c[r[0]]));
	}

	long[][] memo;

	long f(int l, int curC) {
		if (r[l] - (l - 1) < curC)
			return memo[l][curC] = 0;
		if (l == n - 1) {
			if (curC > 1)
				throw new AssertionError();
			return memo[l][curC] = 1;
		}
		if (memo[l][curC] != -1)
			return memo[l][curC];
		long ret = 0;
		if (!(r[l] - (l - 1 + 1) < curC)) {
			ret += f(l + 1, curC + c[r[l + 1]] - c[r[l]]);
		}
		if (!(curC == 0)) {
			ret += f(l + 1, curC - 1 + c[r[l + 1]] - c[r[l]]);
		}
		ret %= MODULO;
		return memo[l][curC] = ret;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}