Problem:
 Score : 500 points    Problem 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 .      Constraints  2 \leq N \leq 10^5  1 \leq K \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K       Output Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7) .        Sample Input 1 3 2      Sample Output 1 9  \gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)  +\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  Thus, the answer is 9 .       Sample Input 2 3 200      Sample Output 2 10813692       Sample Input 3 100000 100000      Sample Output 3 742202979  Be sure to print the sum modulo (10^9+7) .

Solution (Python):
K,N = map(int,(input().split()))
MOD = 10**9+7
core = [0]*(N+1)
tr = [0]*(N+1)

for i in range(1,N+1):
    core[i] = N//i

for i in range(1,N+1)[::-1]:
    if core[i] == 1:
        tr[i] = 1
    else:
        tr[i] = pow(core[i],K,MOD)
        now = i
        r = 2
        while now*r <= N:
            tr[i] -= tr[now*r]
            r += 1

ans = 0
for i in range(1,N+1):
    ans += i * tr[i]
    ans %= MOD

print(ans)

Solution (Python):
n, k = map(int, input().split())

MOD = 10**9 + 7

class mint:
    def __init__(self, i):
        self.i = i

    def __add__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)

    def __radd__(self, m):
        t = self.i + (m.i if isinstance(m, mint) else m)
        if t > MOD:
            t -= MOD
        return mint(t)

    def __mul__(self, m):
        return mint(self.i * m.i % MOD)

    def __sub__(self, m):
        t = self.i - m.i
        if t < 0:
            t += MOD
        return mint(t)

    def __pow__(self, m):
        i = self.i
        res = 1
        while(m > 0):
            if m & 1:
                res = res * i % MOD 
            i = i * i % MOD
            m >>= 1
        return mint(res)

    def __truediv__(self, m):
        return mint(self.i * m ** (MOD - 2) % MOD)

    def __repr__(self):
        return repr(self.i)

l = [mint(0) for _ in range(k + 1)]

for x in range(k, 0, -1):
    count = mint(k // x) ** n
    for tx in range(x + x, k + 1, x):
        count -= l[tx]
    l[x] = count

ans = sum(mint(i) * x for i, x in enumerate(l))
print(ans)

Solution (Python):
N, K = map(int, input().split())
MOD = 1000000007
ans = 0
dp = [0] * (K + 1)
for i in range(K, 0, -1):
    div = K // i
    amount = (pow(div, N, MOD)) % MOD
    for j in range(2, div + 1, 1):
        amount = (amount - dp[j * i] + MOD) % MOD
    dp[i] = amount
    ans = (ans + amount * i) % MOD
print(ans)

Solution (Python):
n,k=map(int,input().split())
m=10**9+7
t=pow(k,n,m)
p=[0,0]
for i in range(2,k+1):
    p.append(pow(k//i,n,m))
for i in range(k,1,-1):
    if 2*i<=k:
        for j in range(2*i,k+1,i):
            p[i]-=p[j]
    t+=(i-1)*p[i]
    t%=m
print(t)

Solution (Python):
import sys
import math

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline

MOD = 10 ** 9 + 7

def main():
    N, K = [int(x) for x in input().split()]

    ans = [0] * (K + 1)
    for i in range(K, 0, -1):
        ans[i] = pow((K // i), N, MOD)
        a = 2
        while i * a <= K:
            ans[i] -= ans[i * a]
            a += 1

    ans2 = 0
    for i in range(1, K + 1):
        ans2 += i * ans[i]
        ans2 %= MOD

    print(ans2)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
mod = int(1e9) + 7
X = [0 for _ in range(K)]
def doubling(n, m):
  y = 1
  base = n
  while m != 0:
    if m % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    m //= 2
  return y
SS = 0
for i in range(K, 0, -1):
  d = K // i
  S = doubling(d, N)
  if d > 1:
    for j in range(2, d+1):
      S -= X[j*i-1]
      S %= mod
  X[i-1] = S
  SS += i * S
  SS %= mod
print(SS)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

MOD = 10**9+7

def main():
    N,K = map(int, readline().split())

    gcd_cnt = [0] * (K+1)

    for i in range(K,1,-1):
        gcd_cnt[i] = pow(K // i, N, MOD)
        x = 2
        while i * x <= K:
            gcd_cnt[i] -= gcd_cnt[i*x]
            gcd_cnt[i] %= MOD
            x += 1

    

    ans = pow(K,N,MOD)
    for i in range(2,K+1):
        ans += ((gcd_cnt[i] % MOD) * (i-1)) % MOD
        ans %= MOD
    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,k = LI()
    f = [1]*(k+1)
    p = 2
    phi = list(range(k+1))
    while p <= k:
        while p <= k and not f[p]:
            p += 1
        j = p
        x = (p-1)*pow(p,mod-2,mod)%mod
        while j <= k:
            phi[j] *= x
            phi[j] %= mod
            f[j] = 0
            j += p
        p += 1
    ans = 0
    for i in range(1,k+1):
        ans += phi[i]*pow(k//i,n,mod)
    print(ans%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
n,k = map(int,input().split())
gcds = []


def power_func(a,n,p):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

mod = 10**9+7
for i in range(k):
    div = k//(k-i)
    count = power_func(div,n, mod)
    for j in range(1,div):
        count = count - gcds[k-((k-i)*(j+1))]
    gcds.append(count)

total = 0

for i in range(k):
    total = (total + (gcds[i]*(k-i)%mod))%mod
print(total)

Solution (Python):
def f1(n):
    divs = []
    for i in range(1, int(n ** 0.5) + 1):  
        if n % i == 0:
            divs.append(i)
            j = n // i
            if i != j:
                divs.append(j)
    return divs


MOD = 10 ** 9 + 7

N, K = map(int, input().split())
ans = 0

X = [0] * (K + 1)

for i in range(K, 0, -1):
    num1 = K // i
    var = pow(num1, N, MOD)
    var -= X[i]
    ans += var * i
    ans %= MOD

    divs = f1(i)
    for d in divs:
        X[d] += var
        X[d] %= MOD
    

print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
result = 0
memo = [0 for _ in range(k+1)]
for i in range(k, 0, -1):
    y = k//i
    z = pow(y, n, mod)
    j = 2
    while j*i<=k:
        z -= memo[j*i]
        z %= mod
        j += 1
    memo[i] = z
    result = (result+z*i)%mod
print(result)

Solution (Python):
n,k = map(int,input().split())
mod = 10**9+7
def pm(a,b):
  return pow(a,b,mod)
table = [0 for i in range(k+1)]
for i in range(1,k+1)[::-1]:
  x = k//i
  table[i] = pm(x,n)
  for j in range(2,x+1):
    table[i] = (table[i]-table[j*i])%mod
ans = 0
for i in range(1,k+1):
  ans = (ans+i*table[i])%mod
print(ans)

Solution (Python):


MOD = 10 ** 9 + 7


N, K = list(map(int, input().split()))


def modpow(x, y):
    res = 1
    while y > 0:
        if y & 1:
            res = res * x % MOD
        x = x * x % MOD
        y >>= 1
    return res


def solve(w, x):
    s = 0
    n = K // x
    for i in range(n, 1, -1):
        y = x * i
        if w[y] == 0:
            solve(w, y)
        s = (s + w[y]) % MOD
    w[x] = modpow(n, N) - s


def main():
    w = [0] * (K + 1)
    for i in range(2, K + 1):
        if w[i]:
            continue
        solve(w, i)
    w[1] = modpow(K, N) - sum(w[2:]) % MOD
    
    ans = 0
    for i in range(1, K + 1):
        ans = (ans + w[i] * i) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):










import sys
sys.setrecursionlimit(10**9)

MOD = int(1e9 + 7)


def main():
    """1~K"""
    n, k = map(int, input().split())
    dp = [-1] * (k + 1)
    
    for x in range(k, 0, -1):
        cnt = k // x
        if cnt == 1:
            dp[x] = 1
        else:
            dp[x] = pow(cnt, n, MOD)
            for i in range(2, cnt + 1):
                dp[x] = (dp[x] - dp[x * i]) % MOD
    ans = 0
    for i in range(1, k + 1):
        ans = (ans + i * dp[i]) % MOD
    print(ans)



if __name__ == "__main__":
    main()

Solution (Python):
N,K=map(int,input().split())
MOD=int(1e9)+7
dp=[0]*(K+1)
for ii in range(K):
    i=K-ii
    dp[i]+=pow(K//i,N,MOD)
    j=2*i
    while j<=K:
        dp[i]=(dp[i]-dp[j]+MOD)%MOD
        j+=i
ans=0
for i in range(1,K+1):
    ans+=dp[i]*i
    ans%=MOD
print(ans)

Solution (Python):
import math
N,K = map(int,input().split())
mod = 10**9+7

def f(n):
  if n == 1:
    return 1
  else:
    a = n
    m = n
    for i in range(2,math.floor(math.sqrt(n))+1):
      if m % i == 0:
        a = a*(i-1)//i
        while m % i == 0:
          m = m // i
        if m == 1:
          break
    if m != 1:
      return a*(m-1)//m
    else:
      return a
      
    
ans = 0  
for i in range(1,K+1):
  ans = (ans + (pow(K//i,N,mod)*f(i))) % mod

print(ans)

Solution (Python):
N, K = map(int, input().split())
MOD = 10**9 + 7

M = int(K ** .5)
f_l = [0] * (M+1)  
f_h = [0] * (M+1)  

def f(k):
  return f_l[k] if k <= M else f_h[K//k]

def compute_f(k):
  x = pow(k, N, MOD)
  sq = int(k ** .5)
  for d in range(2, k+1):
    n = k // d
    if n <= sq:
      break
    x -= f(n)
  for n in range(1, sq+1):
    cnt = k//n - k//(n+1)
    x -= f_l[n] * cnt
  return x

for k in range(1, M+1):
  f_l[k] = compute_f(k)

for d in range(M, 0, -1):
  f_h[d] = compute_f(K//d)

answer = 0

for k in range(1, M+1):
  low_d = K // (k+1) + 1
  high_d = K // k
  items = high_d - low_d + 1
  coef = (low_d + high_d) * items // 2
  answer += coef * f_l[k]
  
for d in range(1, M+1):
  if K // d <= M:
    break
  answer += d * f_h[d]

answer %= MOD
print(answer)

Solution (Python):
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

ans = 0
count = [-1] * (K + 1)
for i in range(K, 0, -1):
    count[i] = pow(K // i, N, MOD) - sum(count[i + i :: i])
    ans += count[i] * i
    ans %= MOD

print(ans)

Solution (Python):
from math import gcd 
N,K=map(int,input().split())

mod=10**9+7

A=[0]*K

for i in range(K,0,-1):
    a=K//i
    b=pow(a,N,mod)
    A[i-1]=b

for i in range(K,0,-1):
    for j in range(K//i-1):
        c=i*(j+2)
        A[i-1]-=A[c-1]
        A[i-1]%=mod

s=0
for i in range(K):
    s+=A[i]*(i+1)
    s%=mod

print(s)

Solution (Python):
n,k=map(int,input().split())
INF=10**9+7
baisu= [[] for _ in [0]*(k+1)]
D=[0]*(k+1)
ans=0
for d in range(1,k+1):
    baisu[d]=[d*i for i in range(2,k//d+1)]
    D[d]=pow(k//d,n,INF)

for d in range(k,0,-1):
    for b in baisu[d]:
        D[d]-=D[b]
    D[d]%=INF
for i,x in enumerate(D):
    
    ans=(ans+i*x)%INF
    


print(ans)

Solution (Python):
def divisors(n):
    ret=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            ret.append(i)
            if i!=n//i:
                ret.append(n//i)
    return ret

mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,1,-1):
    divs=divisors(i)
    cnt[i]+=pow(k//i,n,mod)
    for val in divs:
        if val==i:
            continue
        else:
            cnt[val]-=cnt[i]
cnt[1]+=pow(k,n,mod)
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Solution (Python):
mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,0,-1):
    cnt[i]+=pow(k//i,n,mod)
    for j in range(2,k//i+1):
      cnt[i]-=cnt[i*j]
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Solution (Python):
mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,0,-1):
    cnt[i]+=pow(k//i,n,mod)
    for j in range(2,k//i+1):
      cnt[i]-=cnt[i*j]
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[0]*(k+1)
a=0
for i in range(k,0,-1):
  l[i]=pow(k//i,n,M)-sum(l[::i])
  a+=i*l[i]
print(a%M)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

ans = 0
A = [0] * (K+1)
for x in range(K, 1, -1):
    a = K // x
    A[x] = pow(a, N, MOD)
    i = x
    while i + x <= K:
        i += x
        A[x] -= A[i]
    A[x] %= MOD
    ans += A[x] * x
    ans %= MOD
ans += pow(K, N, MOD) - sum(A)
ans %= MOD
print(ans)

Solution (Python):


MOD = 10**9 +7

N, K = map(int,input().split())

ans = 0
gcd_equal_i = [0]*(K+1) 

for D in range(K, 0, -1):
    num_of_mul = K // D
    tmp = pow(num_of_mul, N, MOD)

    i = 2
    while D*i <= K:
        tmp -= gcd_equal_i[D*i]
        i += 1
    
    gcd_equal_i[D] = tmp
    ans += D*tmp
    ans %= MOD


print(ans)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
d=[0]*(k+1)
a=0
for i in range(k,0,-1):d[i]=pow(k//i,n,M)-sum(d[::i]);a+=i*d[i]
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[0]*(k+1)
a=0
for i in range(k,0,-1):
  l[i]=pow(k//i,n,M)-sum(l[j] for j in range(i*2,k+1,i))
  a+=i*l[i]
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[0]*(k+1)
a=0
for i in range(k,0,-1):
  l[i]=pow(k//i,n,M)-sum(l[j] for j in range(i*2,k+1,i))
  a+=i*l[i]
print(a%M)

Solution (Python):
import math
N,K = map(int,input().split())
mod = 10**9+7

A = [0]*K 
for i in range(K//2,K):
  A[i] = 1
for i in range(K//2,0,-1):
  a = pow(math.floor(K//i),N,mod)
  for j in range(2,math.floor(K//i)+1):
    a -= A[i*j-1]
  A[i-1] = a
      
ans = 0  
for i in range(1,K+1):
  ans = (ans + (A[i-1]*i)) % mod

print(ans)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
l=[0]*(k+1)
a=0
for i in range(k,0,-1):
  l[i]=pow(k//i,n,M)
  for j in range(i*2,k+1,i):
    l[i]-=l[j]
  a+=i*l[i]
print(a%M)

Solution (Python):
MOD = int(1e9+7)
def modpow(a, p, mod):  
  res = 1
  while p > 0:
    if p & 1 > 0:
        res = res * a % mod
    a = a**2 % mod
    p >>= 1
  return res

N, K = map(int, input().strip().split())
res = [-1]*(K+1)  
for x in range(K, 0, -1):
  n = K//x  
  if n == 1: res[x] = 1
  else:
    res[x] = modpow(n, N, MOD)
    for i in range(2,n+1):
      res[x] = (res[x] - res[x*i]) % MOD

ans = 0
for i in range(1, K+1):
  ans = (ans + i*res[i]) % MOD
print(ans)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
d=[0]*-~k
a=0
for i in range(k,0,-1):d[i]=pow(k//i,n,M)-sum(d[::i]);a+=i*d[i]
print(a%M)

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
d=[0]*-~k
a=0
for i in range(k,0,-1):d[i]=pow(k//i,n,M)-sum(d[::i]);a+=i*d[i]
print(a%M)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()

ans = 0
A = [0] * (K+1)
for x in range(K, 1, -1):
    a = K // x
    A[x] = pow(a, N, MOD)
    i = x
    while i + x <= K:
        i += x
        A[x] -= A[i]
    A[x] %= MOD
    ans += A[x] * x
    ans %= MOD
ans += pow(K, N, MOD) - sum(A)
ans %= MOD
print(ans)

Solution (Python):
mod = 10**9+7
N,K = map(int,input().split())
ans = [0]*(K+1)

for k in range(K,0,-1):
    ans[k] = pow(K//k,N,mod)
    for l in range(2,K//k+1):
        ans[k] -= ans[k*l]
    ans[k] %= mod

for i in range(K+1):
    ans[i] *= i

ans = sum(ans)%mod

print(ans)

Solution (Python):
def divisor_enumetarion(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.remove(n)
    return divisors
    
n,k=map(int,input().split())
 
dp=[0]*k
mod=10**9+7
 
ans=0
for i in range(k,0,-1):
    toori=pow(k//i,n,mod)
 
    dp[i-1]+=toori
 
    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]%mod
 
    ans+=(dp[i-1]*i)%mod
print(ans%mod)

Solution (Python):
from math import gcd
n, k = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
cnt = [0 for _ in range(k+1)]
for i in range(k, 0, -1):
    cnt[i] = pow(k // i, n, mod)
    for j in range(2, k // i + 1):
        cnt[i] = (cnt[i] - cnt[i * j]) % mod
for i in range(1, k+1):
    ans = (ans + cnt[i] * i) % mod

print(ans)

Solution (Python):
from fractions import gcd
N,K = list(map(int, input().split()))

S = [0]*(K+1)
ans = [0]*(K+1)

for i in range(K):
    n = K - i
    yakusu = K//n
    s = pow(yakusu,N,1000000007)
    for j in range(2*n,K+1,n):
        s -= S[j]
    S[n] = s%1000000007
    ans[n] = s*n%1000000007



print(sum(ans)%1000000007)

Solution (Python):
MOD = 10**9 + 7

def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x



N, K = map(int, input().split())

X = [0]*(K+1)
for i in range(1, K+1):
    X[i] = modPow(K//i, N, MOD)

for i in range(K, 0, -1):
    for j in range(i*2, K+1, i):
        X[i] -= X[j]

    X[i] %= MOD

print(sum(i*X[i] for i in range(1, K+1))%MOD)

Solution (Python):
from collections import deque, Counter
from itertools import chain, combinations
import json

import bisect
import sys
import math
import bisect

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7


def main():
    
    N, K = [int(a) for a in input().split()]

    ts = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        m = K // k
        ts[k] = pow(m, N, M)
        for k2 in range(k * 2, K + 1, k):
            ts[k] -= ts[k2]
        ts[k] = ts[k] % M
    print(sum([a * i for i, a in enumerate(ts)]) % M)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
mod = 10**9+7

def main():
	n,k = MI()
	dp=[0]*(k+1)
	ans=0
	def g(x, n, mod):
		if n == 0:
			return 1
		K = 1
		while n > 1:
			if n % 2 != 0:
				K *= x
			x *= x%mod
			K %= mod
			n //= 2
		return K * x

	for i in range(k,0,-1):
		dp[i]=g(k//i,n,mod)
		for j in range(i*2,k+1,i):
			dp[i]-=dp[j]
			dp[i]%=mod
		dp[i]=(dp[i]%mod+mod)%mod
		ans+=i*dp[i]%mod
	print(ans%mod)
if __name__ == '__main__':
	main()

Solution (Python):

n,k = list(map(int,input().split()))
MOD = 10**9+7

L = [i for i in range(k+1)]

for i in range(1,k):
    for j in range(i*2,k+1,i):
        L[j]-=L[i]
ans = 0
for i in range(1,k+1):
    ans = (ans+pow(k//i,n,MOD)*L[i])%MOD
print(ans)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9 + 7

cnt = [pow(k // max(i, 1), n, mod) for i in range(k+1)]

for i in range(k, 0, -1):
    for j in range(2*i, k+1, i):
        cnt[i] -= cnt[j]

s = 0
for i in range(k+1):
    s = (s + i*cnt[i]) % mod

print(s)

Solution (Python):
n,k = map(int,input().split())
dp = [0]*k
mod = 10**9 + 7
ans = 0
for i in range(k,0,-1):
    dp[i-1] += pow(k//i,n,mod)
    for j in range(k//i,1,-1):
        dp[i-1] -= dp[i*j-1]
    ans += dp[i-1]*i
    ans %= mod
    
print(ans)

Solution (Python):
mod = 10 ** 9 + 7

n, k = list(map(int, input().split()))
c = {i: pow(k//i, n, mod) for i in range(1, k+1)}
for i in range(k, 0, -1):
    for j in range(2*i, k+1, i):
        c[i] -= c[j]
_sum = 0
for x in range(1, k+1):
    _sum += c[x] * x % mod
print(_sum % mod)

Solution (Python):
def e_sum_of_gcd_of_tuples_hard(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]
    ans = [0] * (K + 1)
    for i in range(K, 0, -1):
        multiple = K // i
        ans[i] = pow(multiple, N, MOD)
        
        for j in range(2 * i, K + 1, i):
            ans[i] -= ans[j]  
        ans[i] %= MOD
    return sum([i * ans[i] for i in range(K + 1)]) % MOD

print(e_sum_of_gcd_of_tuples_hard())

Solution (Python):
M=10**9+7
n,k=map(int,input().split())
d=[0]*-~k
a=0
for i in range(k,0,-1):
    t=c=0
    for j in range(i,k+1,i):
        c+=1
        t+=d[j]
    d[i]=pow(c,n,M)-t
    a=(a+i*d[i])%M
print(a)

Solution (Python):
import sys
input = sys.stdin.readline
from math import gcd

MOD = 10**9+7

n,k = map(int,input().split())
res = 0

c = [0]*(k+1)

for i in range(k,1,-1):
    tmp = pow(k//i,n,MOD)
    for j in range(i*2,k+1,i):
        tmp -= c[j]
    c[i] = tmp%MOD
    res = (res+c[i]*i)%MOD

res = (res+pow(k,n,MOD)-sum(c))%MOD

print(res)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() 

n, K = na()
mod = 1000000007


eqi = [pow(K//(i+1), n, mod) for i in range(K)]

for i in range(K,0,-1):
    if i == 1:
        eqi[i-1] -= sum(eqi[1:])
        break
    
    
    
    for m in range(2,(K//i)+1):
        eqi[i-1] -= eqi[m*i - 1]
    eqi[i-1] %= mod
ans = 0
for i in range(K):
    ans += ((i+1)*eqi[i])%mod
print(ans%mod)

Solution (Python):
MOD = 10**9 + 7


def main():
    N, K = (int(i) for i in input().split())
    ans = 0
    A = [0]*(K+1)
    for i in range(1, K+1)[::-1]:
        A[i] += pow(K//i, N, MOD)
        A[i] %= MOD
        for j in range(2*i, K+1, i):
            A[i] -= A[j]
        ans += i*A[i]
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
ans = [0 for _ in range(K+10)]

MOD = 10**9+7

ts = 0
for i in range(K, 1, -1):
    t = K//i
    ans[i] = (pow(t, N, MOD)+MOD) % MOD
    for j in range(2*i, K+1, i):
        ans[i] -= ans[j]
    ans[i] %= MOD
    ts += ans[i]
ans[1] = (pow(K, N, MOD)-ts+MOD) % MOD

print(sum([i * ans[i] for i in range(K+10)])%MOD)

Solution (Python):
from collections import *
import sys
try: inp = raw_input
except: inp = input
def err(s):
    sys.stderr.write('{}\n'.format(s))

def ni():
    return int(inp())

def nl():
    return [int(_) for _ in inp().split()]

N, K = nl()

MOD = 10**9 + 7
su = 0


sm = 0
muls = [0]*(K+1)
for k in range(K, 0, -1):
    sels = K//k
    pw = pow(sels, N, MOD)
    for mk in range(2*k, K+1, k):
        pw -= muls[mk]
    muls[k] = pw%MOD
    sm += pw*k%MOD

print(sm%MOD)

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
mod = 10**9+7
dp = [1]*(k+1)

for i in range(k//2,0,-1):
    p = pow(k//i,n,mod)
    for j in range(2*i,k+1,i):
        p -= dp[j]
    dp[i] = p%mod

ans = 0

for k,v in enumerate(dp):
    ans += k*v
    ans %= mod

print(ans)

Solution (Python):
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)

for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= sum(nums[(2*i)::i])
    nums[i] += tmp
    
print(sum((i)*nums[i]%M for i in range(len(nums)))%M)

Solution (Python):
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    

print((np.arange(k+1) * nums).sum()%M)

Solution (Python):
n, k = [int(_) for _ in input().split()]
d = {}
ans = 0
for i in range(k, 0, -1):
    
    res = pow(k//i,n,(10**9+7))
    t = 2
    while i * t in d:
        res -= d[i * t]
        t += 1
    res = res % (10**9+7)
    d[i] = res
    ans += res * i
    ans = ans % (10**9+7)
print(ans)

Solution (Python):



from math import gcd
from functools import reduce
from itertools import product 


n,k=map(int,input().split(' '))
 
mod=10**9+7
 
ar=list(range(1,k+1))
ar.reverse()
 
ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)-sum(ans[i*2:k+1:i])
print(sum(i*x for i,x in enumerate(ans))%mod)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, k = list(map(int, readline().split()))

    count = [0] * (k + 1)

    for x in range(k, 0, -1):
        c = k // x
        cx = pow(c, n, MOD)

        y = 2

        while x * y <= k:
            cx -= count[x * y]
            cx %= MOD
            y += 1

        count[x] = cx

    ans = 0
    for i in range(1, k + 1):
        ans += count[i] * i
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
mod = 10**9+7
N, K = map(int, input().split())
cnt = [0]*(K+1)
ans = 0
for x in range(K, 1, -1):
    c = pow(K//x, N, mod)
    a = 2
    while a*x <= K:
        c -= cnt[a*x]
        a += 1
    ans = (ans+x*c%mod)%mod
    cnt[x] = c
ans = (ans+pow(K, N, mod)-sum(cnt))%mod
print(ans)

Solution (Python):



from math import gcd
from functools import reduce
from itertools import product 


n,k=map(int,input().split(' '))
 
mod=10**9+7
 
ar=list(range(1,k+1))
ar.reverse()
 
ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)-sum(ans[slice(i*2,k+1,i)])
print(sum(i*x for i,x in enumerate(ans))%mod)

Solution (Python):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
GCDs = [-1] * (K + 1)

ans = 0
for i in range(K, 0, -1):
    num = K // i
    GCDs[i] = pow(num, N, MOD)
    for n in range(2, num + 1):
        GCDs[i] -= GCDs[i * n] % MOD
    ans = (GCDs[i] * i % MOD + ans) % MOD

print(ans)

Solution (Python):
M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N, K = map(int, input().split())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    
    
    
    main()

Solution (Python):
N, K = map(int, input().split())

mod = 10 ** 9 + 7

memo = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
    memo[i] = pow(K // i, N, mod)
    j = 2
    while i * j <= K:
        memo[i] -= memo[i * j]
        j += 1
    ans += memo[i] * i
    ans %= mod

print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'

    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase

input=lambda: sys.stdin.readline().rstrip()



def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret




def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True

n,k=LI()
c=[0]*(1+k)

for i in range(k,0,-1):
    x=k//i
    c[i]=pow(x,n,mo)
    j=2
    while j*i<=k:
        c[i]-=c[i*j]
        c[i]%mo
        j+=1

ans=0
for i in range(1,k+1):
    ans+=c[i]*i
    ans%=mo

print(ans)