output_description: Print Q lines. The i-th line should contain the answer to the i-th query.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N Q
      S
      l_1 r_1
      :
      l_Q r_Q
attempt: import sys
  
  sys.setrecursionlimit(10**7)
  INF = 10**18
  MOD = 10**9 + 7
  
  
  def LI():
      return [int(x) for x in sys.stdin.readline().split()]
  
  
  def LI_():
      return [int(x) - 1 for x in sys.stdin.readline().split()]
  
  
  def LF():
      return [float(x) for x in sys.stdin.readline().split()]
  
  
  def LS():
      return sys.stdin.readline().split()
  
  
  def II():
      return int(sys.stdin.readline())
  
  
  def SI():
      return input()
  
  
  from itertools import product
  
  
  def main():
      N = II()
      A, G, C, T = range(4)
  
      def code(c0, c1, c2):
          return c0 + 4 * c1 + 16 * c2
  
      dp = [0] * 64
      dp[code(T, T, T)] = 1
      for _ in range(N):
          tmp = [0] * 64
          for p1, p2, p3 in product(range(4), repeat=3):
              for cur in range(4):
                  if (p2, p1, cur) == (A, G, C):
                      continue
                  if (p2, p1, cur) == (A, C, G):
                      continue
                  if (p2, p1, cur) == (G, A, C):
                      continue
                  if (p3, p1, cur) == (A, G, C):
                      continue
                  if (p3, p2, cur) == (A, G, C):
                      continue
                  tmp[code(cur, p1, p2)] += dp[code(p1, p2, p3)]
                  tmp[code(cur, p1, p2)] %= MOD
          dp = tmp
      ans = sum(dp)
  
      return ans % MOD
  
  
  print(main())
  
problem_description: Statement
  
  You are given a string S of length N consisting of `A`, `C`, `G` and `T`.
  Answer the following Q queries:
  
    * Query i (1 \leq i \leq Q): You will be given integers l_i and r_i (1 \leq l_i < r_i \leq N). Consider the substring of S starting at index l_i and ending at index r_i (both inclusive). In this string, how many times does `AC` occurs as a substring?
samples: [{"input": "8 3\n    ACACTACG\n    3 7\n    2 3\n    1 8", "output": "2\n    0\n    3\n    \n\n  * Query 1: the substring of S starting at index 3 and ending at index 7 is `ACTAC`. In this string, `AC` occurs twice as a substring.\n  * Query 2: the substring of S starting at index 2 and ending at index 3 is `CA`. In this string, `AC` occurs zero times as a substring.\n  * Query 3: the substring of S starting at index 1 and ending at index 8 is `ACACTACG`. In this string, `AC` occurs three times as a substring."}]