output_description: Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N K
attempt: def resolve():
      n = int(input())
      s = input()
      r = [0] * n
      g = [0] * n
      b = [0] * n
      for i in range(n):
          if s[i] == "R":
              r[i] = 1
          elif s[i] == "G":
              g[i] = 1
          else:
              b[i] = 1
      ans = 0
      a = [r, g, b]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
      a = [r, b, g]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
      a = [g, r, b]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
      a = [g, b, r]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
  
      a = [b, r, g]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
  
      a = [b, g, r]
      for i in range(n):
          if a[0][i] == 1:
              for j in range(i + 1, n):
                  if a[1][j] == 1:
                      ans += sum(a[2][j + 1 : n])
  
      for i in range(1, n // 2 + 1):
          j = 0
          while j + 2 * i <= n - 1:
              if {s[j], s[j + i], s[j + 2 * i]} == {"R", "G", "B"}:
                  ans -= 1
              j += 1
      print(ans)
  
  
  resolve()
  
problem_description: Statement
  
  Consider sequences \\{A_1,...,A_N\\} of length N consisting of integers
  between 1 and K (inclusive).
  
  There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of
  them.
  
  Since this sum can be enormous, print the value modulo (10^9+7).
  
  Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.
samples: [{"input": "3 2", "output": "9\n    \n\n\\gcd(1,1,1)+\\gcd(1,1,2)+\\gcd(1,2,1)+\\gcd(1,2,2)\n+\\gcd(2,1,1)+\\gcd(2,1,2)+\\gcd(2,2,1)+\\gcd(2,2,2) =1+1+1+1+1+1+1+2=9\n\nThus, the answer is 9.\n\n* * *"}, {"input": "3 200", "output": "10813692\n    \n\n* * *"}, {"input": "100000 100000", "output": "742202979\n    \n\nBe sure to print the sum modulo (10^9+7)."}]