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: # E
  N, K = map(int, input().split())
  MOD = 10**9 + 7
  # e.g.
  # N=3,K=4
  #   gcd(A)=4 -> (4,4,4)=1**3=1
  #   gcd(A)=3 -> (3,3,3)=1**3=1
  #   gcd(A)=2 -> (2or4,2or4,2or4)-(4,4,4)=2**3-1**3=7
  #   gcd(A)=1 -> (1~4,1~4,1~4)-上全部=4**3-(2**3-1**3)-1**3-1**3=55
  # and=1*4+1*3+7*2+55*1=76
  #
  # gcd(A)=xとなるAをx=K,K-1,...,1として数えていく。
  # A=(x or 2x or 3x or ...,x or 2x or 3x or ...,...)という形をしているが
  # 2x,3x,...がK以下ならxより大きい場合で既にカウントしてしまっている
  # (gcd(2x,2x)=2xをgcd(2x,2x)=xとして数えてしまっている)
  # ->2x,3xについてカウント済みならそれを引けばいい: Kから数えればいい
  
  ans = 0  # 出力する答え
  GCD = [0 for _ in range(K + 1)]  # GCD[i]:gcd(A)=iとなるAの総数
  for x in range(K, 0, -1):  # gcd(A)=xとなるAを各xで数える
      Ai_cnt = K // x  # 各Aiについてとりうる値の総数(x,2x,3x,...<=K)
      rep = 0  # 既にカウント済みなものをここに数えてまとめておく
  
      # 既にカウント済みがあるか数える
      check = 2 * x
      while check <= K:  # これを満たすならK以下である
          rep += GCD[check]  # 満たしたのでrepに足す
          check += x  # 次のxの倍数について調べるために足す
  
      # repができたのでGCD[i]に記録
      GCD[x] = pow(Ai_cnt, N, MOD) - rep  # 繰り返し2乗法: O(logN)
      # kについては完成したので,ansに足す
      ans += x * (GCD[x])
      ans %= MOD
  # 出力する前に計算量の確認
  # 計算量はおよそ各xでK//x回の計算とpowが必要なので
  #   sum(log(N)+K//x x:1toK)
  # <=K*(log_2(N)+sum(1/x 1toK))
  # ~ K*(log_2(N)+log_e(K))
  # < (10**5)*(2*log_2(10**5))
  # < 4*10**6
  # よってギリ間に合うと思われる
  print(ans)
  
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)."}]