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: MOD = 10**9 + 7
  e, N = map(int, input().split())
  
  
  def phi_table(N):
      phi = list(range(N + 1))
      for p in range(2, N + 1):
          if phi[p] == p:
              for n in range(N // p, 0, -1):
                  phi[p * n] -= phi[n]
      return phi
  
  
  L = int(N**0.66)
  H = int(N // (L + 1))
  phi = phi_table(L)
  
  # f(n) = \sum_{i=1}^n phi(i)
  
  f_l = phi.copy()
  for n in range(L):
      f_l[n + 1] += f_l[n]
  
  f_h = [0] * (H + 1)  # f(N//d)
  
  
  def f(n):
      return f_l[n] if n <= L else f_h[N // n]
  
  
  def compute_f(n):
      sq = int(n**0.5)
      x = n * (n + 1) // 2
      for d in range(1, n + 1):
          m = n // d
          if m <= sq:
              break
          x -= f(m)
      for m in range(1, sq + 1):
          cnt = n // m - n // (m + 1)
          x -= f_l[m] * cnt
      return x
  
  
  for d in range(H, 0, -1):
      f_h[d] = compute_f(N // d)
  
  sq = int(N**0.5)
  answer = 0
  for d in range(1, N + 1):
      n = N // d
      if n <= sq:
          break
      answer += pow(n, e, MOD) * phi[d]
  
  for n in range(1, sq + 1):
      low_d = N // (n + 1)
      high_d = N // n
      phi_sum = f(high_d) - f(low_d)
      answer += phi_sum * pow(n, e, MOD)
  
  answer %= MOD
  print(answer)
  
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)."}]