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 <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<int> a(n, 0);
  for(int i = 0; i < m; i++)
  {
    int li, ri;
    cin >> li >> ri;
    li--;
    ri--;
    a[li] = max(a[li], ri);
  }
  for(int i = 1; i < n; i++)
  {
    a[i] = max(max(a[i], a[i - 1]), i);
  }
  vector<int> pref(n);
  pref[0] = s[0] - '0';
  for(int i = 1; i < n; i++)
  {
    pref[i] = pref[i - 1] + s[i] - '0';
  }
  vector<vector<int>> dp(n + 1, vector<int> (n + 1, 0));
  dp[n][0] = dp[n - 1][0] = dp[n - 1][1] = 1;
  for(int i = n - 2; i >= 0; i--)
  {
    int offset = pref[a[i + 1]] - pref[a[i]], lim = min(n, a[i] - i + 1);
    for(int j = 0; j <= lim; j++)
    {
      if(j == 0)
      {
        (dp[i][j] += dp[i + 1][j + offset]) %= MOD;
      }
      else if(j == lim)
      {
        (dp[i][j] += dp[i + 1][j - 1 + offset]) %= MOD;
      }
      else
      {
        (dp[i][j] += dp[i + 1][j + offset]) %= MOD;
        (dp[i][j] += dp[i + 1][j - 1 + offset]) %= MOD;
      }
    }
  }
  cout << dp[0][pref[a[0]]] << endl;
  return 0;
}