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: #!/usr/bin/env python3
  
  
  M = 10**9 + 7
  
  
  def solve(n, m, s, lst):
  
      cnt = [0] * n
      t = 0
      for i in range(n):
          if s[i] == "1":
              t += 1
          cnt[i] = t
  
      dp = [[0] * (n + 1) for _ in range(n + 1)]
      dp[0][0] = 1
      r = 0
      j = 0
      for i in range(n):
          while j < m:
              lj, rj = lst[j]
              if lj <= i:
                  r = max(r, rj)
                  j += 1
              else:
                  break
          if r <= i:
              c = cnt[i]
              if 0 < c:
                  dp[i + 1][cnt[i]] = dp[i][c] + dp[i][c - 1]
              else:
                  dp[i + 1][0] = dp[i][0]
          else:
              for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                  if 0 < k:
                      dp[i + 1][k] = dp[i][k] + dp[i][k - 1]
                  else:
                      dp[i + 1][0] = dp[i][0]
  
      return dp[n][cnt[n - 1]]
  
  
  def main():
      n, m = input().split()
      n = int(n)
      m = int(m)
      s = input()
      lst = []
      for _ in range(m):
          l, r = input().split()
          l = int(l) - 1
          r = int(r) - 1
          lst.append((l, r))
  
      print(solve(n, m, s, lst))
  
  
  if __name__ == "__main__":
      main()
  
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"}]