output_description: Print the letter representing the base that bonds with the base b.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      b
attempt: from functools import lru_cache
  
  MOD = 1000000007
  
  
  def valid(s):
      f = 0
      if len(s) == 4:
          f = 1
          if (s[0] == "A" and s[2:] == "GC") or (s[0:2] == "AG" and s[3] == "C"):
              return 0
      return s[f:] != "AGC" and s[f:] != "ACG" and s[f:] != "GAC"
  
  
  @lru_cache(maxsize=None)
  def dfs(n, s):
      if not valid(s):
          return 0
  
      if n == N:
          return 1
  
      f = len(s) == 4
      a = dfs(n + 1, s[f:] + "A")
      b = dfs(n + 1, s[f:] + "C")
      c = dfs(n + 1, s[f:] + "G")
      d = dfs(n + 1, s[f:] + "T")
      return (a + b + c + d) % MOD
  
  
  N = int(input())
  ans = dfs(0, "")
  print(ans)
  
problem_description: Statement
  
  On the Planet AtCoder, there are four types of bases: `A`, `C`, `G` and `T`.
  `A` bonds with `T`, and `C` bonds with `G`.
  
  You are given a letter b as input, which is `A`, `C`, `G` or `T`. Write a
  program that prints the letter representing the base that bonds with the base
  b.
samples: [{"input": "A", "output": "T\n    \n\n* * *"}, {"input": "G", "output": "C"}]