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: class UnionFind:
      def __init__(self, n):
          self.par = [i for i in range(n + 1)]
          self.rank = [0] * (n + 1)
          self.size = [1] * (n + 1)
  
      # 譬ｹ繧呈､懃ｴ｢縺吶ｋ髢｢謨ｰ
      def find(self, x):
          if self.par[x] == x:
              return x
          else:
              self.par[x] = self.find(self.par[x])
              return self.find(self.par[x])
  
      # 邨仙粋(unite)縺吶ｋ髢｢謨ｰ
      def unite(self, x, y):
          x = self.find(x)
          y = self.find(y)
          if x == y:
              return
          if self.rank[x] < self.rank[y]:
              self.par[x] = y
              self.size[y] += self.size[x]
          else:
              self.par[y] = x
              self.size[x] += self.size[y]
              if self.rank[x] == self.rank[y]:
                  self.rank[x] += 1
  
      # 蜷後§繧ｰ繝ｫ繝ｼ繝励↓螻槭☆繧九°繧貞愛螳壹☆繧矩未謨ｰ
      def same_check(self, x, y):
          return self.find(x) == self.find(y)
  
      # 隕∫ｴ縺悟ｱ槭☆繧区惠縺ｮ豺ｱ縺輔ｒ霑斐☆髢｢謨ｰ
      def get_depth(self, x):
          return self.rank[self.find(x)]
  
      # 隕∫ｴ縺悟ｱ槭☆繧区惠縺ｮ繧ｵ繧､繧ｺ繧定ｿ斐☆髢｢謨ｰ
      def get_size(self, x):
          return self.size[self.find(x)]
  
      # 繧ｰ繝ｫ繝ｼ繝玲焚繧定ｿ斐☆髢｢謨ｰ
      def group_sum(self):
          c = 0
          for i in range(len(self.par)):
              if self.find(i) == i:
                  c += 1
          return c
  
  
  if __name__ == "__main__":
      N, K, L = map(int, input().split())
      uf = UnionFind(N)
  
      for i in range(K):
          p, q = [int(i) for i in input().split()]
          uf.unite(p, q)
  
      ans = [1] * N
      for i in range(L):
          r, s = [int(i) for i in input().split()]
          if uf.same_check(r, s):
              ans[r - 1] += 1
              ans[s - 1] += 1
  
      print(*ans)
  
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"}]