output_description: Print the number of the possible values for S after the M operations, modulo
  1000000007.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N M
      S
      l_1 r_1
      :
      l_M r_M
attempt: #include <iostream>
  #include <cstdio>
  #include <cstdlib>
  #include <algorithm>
  using namespace std;
   
  typedef long long ll;
  const int MOD = (int)1e9 + 7;
  int add(int x, int y)
  {
  	x += y;
  	if (x >= MOD) return x - MOD;
  	return x;
  }
  int sub(int x, int y)
  {
  	x -= y;
  	if (x < 0) return x + MOD;
  	return x;
  }
  int mult(int x, int y)
  {
  	return ((ll)x * y) % MOD;
  }
   
  const int N = 3030;
  int n;
  char s[N];
  int a[N];
  int b[N];
  int dp[N][N];
  int C[N][N];
   
  void read()
  {
  	int m;
  	scanf("%d%d", &n, &m);
  	scanf(" %s ", s);
  	for (int i = 0; i < n; i++)
  		a[i] = (int)(s[i] - '0');
  	for (int i = 0; i < n; i++)
  		b[i] = i + 1;
  	while(m--)
  	{
  		int l, r;
  		scanf("%d%d", &l, &r);
  		l--;
  		b[l] = max(b[l], r);
  	}
  	for (int i = 1; i < n; i++)
  		b[i] = max(b[i], b[i - 1]);
  }
   
  int main()
  {
  	read();
   
  	for (int i = 0; i < N; i++)
  		C[i][0] = C[i][i] = 1;
  	for (int i = 1; i < N; i++)
  		for (int j = 1; j < i; j++)
  			C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
  	
  	dp[0][0] = 1;
  	int cur = 0;
  	for (int i = 0; i < n; i++)
  	{
  		int willAdd = 0;
  		while(cur < b[i])
  		{
  			willAdd += a[cur];
  			cur++;
  		}
  		for (int x = 0; x <= n; x++)
  		{
  			if (dp[i][x] == 0) continue;
  			int y = x + willAdd;
  			if (y != 0)
  				dp[i + 1][y - 1] = add(dp[i + 1][y - 1], dp[i][x]);
  			if (y != cur - i)
  				dp[i + 1][y] = add(dp[i + 1][y], dp[i][x]);
  		}
  	}
  	printf("%d\n", dp[n][0]);
   
  	return 0;
  }
problem_description: Statement
  
  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)?
samples: [{"input": "5 2\n    01001\n    2 4\n    3 5", "output": "6\n    \n\nAfter the first operation, S can be one of the following three: `01001`,\n`00101` and `00011`.\n\nAfter the second operation, S can be one of the following six: `01100`,\n`01010`, `01001`, `00011`, `00101` and `00110`.\n\n* * *"}, {"input": "9 3\n    110111110\n    1 4\n    4 6\n    6 9", "output": "26\n    \n\n* * *"}, {"input": "11 6\n    00101000110\n    2 4\n    2 3\n    4 7\n    5 6\n    6 10\n    10 11", "output": "143"}]