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: # coding: utf-8
  # Your code here!
  import sys
  
  sys.setrecursionlimit(10**6)
  readline = sys.stdin.readline
  read = sys.stdin.read
  
  
  def Eratosthenes(N):  # N以下の素数のリストを返す
      N += 1
      is_prime_list = [True] * N
      m = int(N**0.5) + 1
      for i in range(3, m, 2):
          if is_prime_list[i]:
              is_prime_list[i * i :: 2 * i] = [False] * ((N - i * i - 1) // (2 * i) + 1)
      return [2] + [i for i in range(3, N, 2) if is_prime_list[i]]
  
  
  # p,n,k,b,*a = [int(i) for i in read().split()]
  
  # k以下、長さn
  n, k = map(int, input().split())
  
  MOD = 10**9 + 7
  res = [0] + [pow(k // i, n, MOD) for i in range(1, k + 1)]
  
  p = Eratosthenes(k)
  
  # print(res)
  for i in p:
      for j in range(i, k + 1, i):
          res[j // i] -= res[j]
  
  # print(res)
  print(sum(ri * i for i, ri in enumerate(res)) % MOD)
  
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)."}]