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):
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()
    G = [0]*(K+1)
    ans = 0
    for i in range(K,0,-1):
        g = pow(K//i,N,mod)
        for l in range(2,(K//i)+1):
            g -= G[i*l]
            if g<0:
                g += mod
        G[i] = g
        ans += g*i
        ans %= mod
    print(ans)
    
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    
    print(ans)
    return

def examF2():
    N = I()
    A = LI()

    dp = [[-inf]*3 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    dp[1][0] = -inf
    dp[1][1] = 0
    dp[1][2] = A[0]
    for i in range(1,N):
        dp[i+1][2] = A[i] + dp[i-1][2]
        dp[i+1][1] = max(A[i] + dp[i-1][1],dp[i][2])
        dp[i+1][0] = max(A[i] + dp[i-1][0],dp[i][1])
    if N%2==1:
        ans = max(dp[-1][0],dp[-1][1])
    else:
        ans = max(dp[-1][1],dp[-1][2])
    
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
27
18 18 19 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49
"""

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

Solution (Python):
n,k=map(int,input().split())
dlist=[[]for i in range(k+1)]
mod = 10**9+7
num=[0]*(k+1)
idx=0
for i in range(1,k+1):
    num[i]=pow(k//i,n,mod)
    for p in range(i*2,k+1,i):
        dlist[p].append(i)
for i in range(k,0,-1):
    for d in dlist[i]:
        num[d]=(num[d]-num[i])%mod
print(sum([i*x for i,x in enumerate(num)])%mod)

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

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

A = [0] * (K + 1)
for d in range(1, K + 1):
    A[d] = pow(K // d, N, MOD)

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

answer = sum(d * x for d, x in enumerate(A))
print(answer % MOD)

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

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

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

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

Solution (Python):



N, K = [int(x) for x in input().split()]
countBcd = [0]*(K+1)
mod=10**9+7
sumTotal=0
for i in range(K,0,-1):
    countBcd[i] = pow(K//i,N,mod)

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

    sumTotal += i*countBcd[i]%mod

print(sumTotal%mod)

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

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

D = [0]*(k+1)
ans = 0
for i in reversed(range(1, k+1)):
    a = k//i
    d = power(a, n, mod)
    j = 1
    while i*j <= k:
        d -= D[i*j]
        j += 1
    D[i] = d
    ans += (d*i)%mod

print(ans%mod)

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

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

D = [0]*(k+1)
ans = 0
for i in reversed(range(1, k+1)):
    a = k//i
    d = power(a, n, mod)
    j = 1
    while i*j <= k:
        d -= D[i*j]
        j += 1
    D[i] = d
    ans += (d*i)%mod

print(ans%mod)

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

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

mod = 1000000007


def fpow(x, power, mod):
    x %= mod
    ans = 1
    while power != 0:
        if (power & 1) == 1:
            ans = ans * x % mod
        power >>= 1
        x = x * x % mod
    return ans


def fac(x):
    A = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            A.append(i)
            if (x // i) != i:
                A.append(x // i)
        i += 1
    return A


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

A = [0] * (k + 2)
ans = 0
for i in range(k, 0, -1):
    
    A[i] += fpow(k // i, n, mod)
    while A[i] < 0:
        A[i] += mod
    A[i] %= mod
    ans = ans + A[i] * i
    ans %= mod
    B = fac(i)
    for b in B:
        if b!=i:
            A[b] -= A[i]

print(ans)

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

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

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


for i in range(k+1):
    ans += list[i] * i % mod

print(ans%mod)

Solution (Python):
MOD = 1000000007
N, K = map(int, input().split())
ans = 0
f = [0] * (K+1)
g = [0] * (K+1)
for t in range(K, 0, -1):
    f[t] = pow(K//t, N, MOD)
    g[t] = f[t]
    for s in range(2 * t, K+1, t):
        g[t] -= g[s]
    ans = (ans + t * g[t]) % MOD
print(ans)

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

Solution (Python):
def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


mod = 10 ** 9 + 7
N, K = map(int, input().split())
LUT, ans = [0] * (K + 1), 0
for g in range(K, 0, -1):
    LUT[g] = modpow(K // g, N, mod)
    LUT[g] = (LUT[g] - sum([LUT[i] for i in range(g * 2, K + 1, g)])) % mod
for i in range(K + 1):
    ans = (ans + i * LUT[i]) % mod
print(ans)

Solution (Python):
MOD = 1000000007

n, k = map(int, input().split())
ans = [0 for i in range(k+1)]
for i in range(k,0,-1):
    t = 0
    for j in range(2*i, k+1, i):
        t = (t + ans[j]) % MOD
    ans[i] = (pow(k//i, n, MOD) - t + MOD) % MOD
sm = 0
for i in range(1, k+1):
    sm = (sm + (i*ans[i]) % MOD) % MOD
print(sm % MOD)

Solution (Python):

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

MOD = 10**9+7


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


print(ans)

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

for i in reversed(range(1, k+1)):
    for j in range(2*i, k+1, i):
        d[i] -= d[j]
        d[i] %= MOD

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

Solution (Python):
n, k = map(int, input().split())
MOD = 1000000007
ans = 0
c = {}
for i in range(k, 0, -1):
    t = pow(k // i, n, MOD)
    m = 2
    while i * m <= k:
        t -= c[i * m]
        m += 1
    c[i] = t % MOD
print(sum([k * v for k, v in c.items()]) % MOD)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


n,k = inpl()
res = 0
cnt = [0] * (k+5)
for i in reversed(range(1,k+1)):
    tmp = pow(k//i,n,mod)
    cnt[i] = tmp
    now = i
    while True:
        now += i
        if now > k:
            break
        cnt[i] -= cnt[now]
    res += cnt[i] * i
    res %= mod
print(res)

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

Solution (Python):
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))

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

m = 10**9+7

def f(n, k):
  res = 0
  lst = [0]*(k+1)
  for i in range(k, 0, -1):
    lst[i] = pow((k//i), n, m) - sum(lst[i*j] for j in range(2, k//i+1))%m
    res += i*lst[i]
    res %= m
  return res

print(f(n, k))

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

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

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

Solution (Python):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [0] * (k + 1)

for i in range(1, k + 1):
    d[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):  
    for j in range(i * 2, k + 1, i):  
        
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Solution (Python):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [0] * (k + 1)

for i in range(1, k + 1):
    d[i] = pow(k // i, n, MOD)

for i in range(k, 0, -1):  
    for j in range(i * 2, k + 1, i):  
        
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Solution (Python):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) if i > 0 else 0 for i in range(0, k + 1)]

for i in range(k, 0, -1):  
    for j in range(i * 2, k + 1, i):  
        
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

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

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

print(sum([i*f for i,f in enumerate(G)]) % mod)

Solution (Python):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  
    for j in range(i * 2, k + 1, i):  
        
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

Solution (Python):

MOD = 1000000007
n, k = [int(x) for x in input().split()]
d = [pow(k // i, n, MOD) for i in range(1, k + 1)]
d.insert(0, 0)

for i in range(k, 0, -1):  
    for j in range(i * 2, k + 1, i):  
        
        d[i] -= d[j]
        d[i] %= MOD
ans = 0
for i, item in enumerate(d):
    ans += i * item
    ans %= MOD
print(ans)

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

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

for i in range(k, 0, -1):
    kin = 1  
    nn = k//i    
    ii = n
    kini = nn
    while ii > 0:
        if ii%2 == 1:
            kin = (kin*kini)%mod
        kini = (kini**2)%mod
        ii //= 2
    for j in range(2,nn+1):
        kin = (kin-kosu[j*i])%mod
    kosu[i] = kin

for i in range(1,k+1):
    ans = (ans+(kosu[i]*i)%mod)%mod

print(ans)

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

if __name__ == '__main__':
    main()

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

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

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n,k=map(int,input().split())
mod=10**9+7
A=[0]*(k+1)
for i in range(1,k+1)[::-1]:
  cur=pow(k//i,n,mod)
  for j in range(2,k+1):
    if i*j>k:
      break
    else:
      cur-=A[i*j]
  A[i]=cur
ans=0
for i in range(1,k+1):
  ans=(ans+i*A[i])%mod
print(ans)

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

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




res = [0] * (K+1)
DIV = 10 ** 9 + 7
for x in range(K,0,-1):
  
  
  
  res[x] = pow(K//x,N,DIV)
  for i in range(x*2,K+1,x):
    res[x] -= res[i]
    
ans = 0
for i in range(len(res)):
  ans += res[i] * i
  ans %= DIV
  
print(ans)

Solution (Python):
N,K = [int(x) for x in input().split()]
count = [0]*(K+1)
ans = 0
mod = 1000000007
for i in range(K,0,-1):
    kosuu = pow(K//i,N,mod)
    if K // i >= 2:
        for j in range(K//i,1,-1):
            kosuu -= count[j*i]
    ans += i*kosuu
    count[i] = kosuu
print(ans%mod)

Solution (Python):

N,K=map(int,input().split())
li=[0]*(K+1)
out=0
mod=10**9+7

for i in range(K,0,-1):
    li[i]=pow(K//i,N,mod)
    for j in range(i*2,K+1,i):
        li[i]-=li[j]
    out+=li[i]*i

print(out%mod)

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

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

Solution (Python):
N,K=map(int,input().split())
MOD=int(1e9)+7

dp=[0]*(K+1)
for i in range(K):
  j=K-i
  dp[j]+=pow(K//j, N, MOD)

  k=2*j
  while k<=K:
    dp[j]=(dp[j]-dp[k]+MOD) % MOD
    k+=j

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

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

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

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

if __name__ == "__main__":
    main()

Solution (Python):
N,K = map(int,input().split())
m = 10**9 + 7
ans = 0
cnt_arr = [0]*(K+1)
for i in range(K,0,-1):
  cnt = pow(int(K//i), N, mod=m)
  j = 2
  while i*j<=K:
    cnt -= cnt_arr[i*j]
    j+=1
  cnt_arr[i]=cnt
  ans += i*cnt

print(int(ans%m))

Solution (Python):





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

modulus = 10 ** 9 + 7

def expt(x, k):
    """(x ** k) % modulus"""
    p = 1
    for b in (bin(k))[2:]:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p


nseq = [expt((k // i), n) if i > 0 else None for i in range(k + 1)]

for i in range(k, 0, -1):
    
    s = sum(nseq[m] for m in range(2 * i, k + 1, i))
    nseq[i] = (nseq[i] - s % modulus + modulus) % modulus


ans = sum(i * nseq[i] % modulus for i in range(1, k + 1))
print(ans % modulus)

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

def bekizyo(x, n): 
    n2 = format(n, "b")
    l_n2 = len(n2)
    ass = 1
    y = x
    for i in range(l_n2):
        if n2[l_n2 - 1 - i] == "1":
            ass *= y
            ass %= mod
        y **= 2
        y %= mod
    return ass


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

l = [0] * (k+1)

for i in range(k, 0, -1):
    num = bekizyo(k//i, n)
    for j in range(k//i - 1):
        num -= l[i * (j+2)]
        num %= mod
    l[i] = num

ans = 0

for i in range(1, k+1):
    ans += i * l[i]
    ans %= mod

print(ans)

Solution (Python):
N, K = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
count = [0] * (K+10)
for i in range(K,0,-1):
    t = pow(K//i, N, mod)
    j = 2
    while j * i <= K:
        t -= count[j*i]
        j += 1
    count[i] = t
    
    ans += t * i
    ans %= mod

print(ans)

Solution (Python):
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))

Solution (Python):
from functools import reduce

mod = 10 ** 9 + 7
def madd(x, y):
    ret = x + y
    return ret if ret < mod else ret - mod
def msub(x, y):
    ret = mod + x - y
    return ret if ret < mod else ret - mod
def mmul(x, y):
    return (x * y) % mod
def mpow(x, n):
    ret = 1
    while n > 0:
        if n & 1 > 0:
            ret *= x
            ret %= mod
        x = (x * x) % mod
        n >>= 1
    return ret

def msum(a):
    return reduce(madd, a, 0)

n, k = map(int, input().split())
INF = - (2**60)
dp = [-INF] * (k + 1)

for g in range(k, 0, -1):
    dp[g] = msub(mpow(k // g, n), msum(dp[2 * g::g]))

print(msum([mmul(g, dp[g]) for g in range(1, k + 1)]))

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, K):
    ans = 0
    M = Mod(10**9+7)

    c = {}
    for k in range(K, 0, -1):
        n = M.pow(K//k, N)
        for j in range(2, K//k+1):
            n = M.sub(n, c[j*k])
        ans = M.add(ans, M.mul(n, k))
        c[k] = n

    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()

Solution (Python):

import math
import sys
import itertools
sys.setrecursionlimit(10**7)

MOD = 1000000007  

class Factorial:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorials = [1, 1]  
        self.invModulos = [0, 1]  
        self.invFactorial_ = [1, 1]  

    def calc(self, n):
        if n <= -1:
            print("Invalid argument to calculate n!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.factorials):
            return self.factorials[n]
        nextArr = [0] * (n + 1 - len(self.factorials))
        initialI = len(self.factorials)
        prev = self.factorials[-1]
        m = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = prev * i % m
        self.factorials += nextArr
        return self.factorials[n]

    def inv(self, n):
        if n <= -1:
            print("Invalid argument to calculate n^(-1)")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        p = self.MOD
        pi = n % p
        if pi < len(self.invModulos):
            return self.invModulos[pi]
        initialI = len(self.invModulos)
        for i in range(initialI, min(p, n + 1)):
            next = -self.invModulos[p % i] * (p // i) % p
            self.invModulos.append(next)
        return self.invModulos[pi]

    def invFactorial(self, n):
        if n <= -1:
            print("Invalid argument to calculate (n^(-1))!")
            print("n must be non-negative value. But the argument was " + str(n))
            exit()
        if n < len(self.invFactorial_):
            return self.invFactorial_[n]
        self.inv(n)  
        nextArr = [0] * (n + 1 - len(self.invFactorial_))
        initialI = len(self.invFactorial_)
        prev = self.invFactorial_[-1]
        p = self.MOD
        for i in range(initialI, n + 1):
            prev = nextArr[i - initialI] = (prev * self.invModulos[i % p]) % p
        self.invFactorial_ += nextArr
        return self.invFactorial_[n]


class Combination:
    def __init__(self, MOD):
        self.MOD = MOD
        self.factorial = Factorial(MOD)

    def choose_k_from_n(self, n, k):
        if k < 0 or n < k:
            return 0
        k = min(k, n - k)
        f = self.factorial
        return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def pow(a,n,m):
    if n == 1:
        return a
    elif n == 0 or a == 1:
        return 1
    else:
        if n%2 == 0:
            r = pow(a,n//2,m)
            return r*r%m
        else:
            r = pow(a,n-1,m)
            return a*r%m

def solve(N: int, K: int):
    powDict = {}
    def powd(a):
        if a in powDict:
            return powDict[a]
        else:
            powDict[a] = pow(a,N,MOD)
            return powDict[a]
    cDict = {}
    sum = 0
    for p in range(K,0,-1):
        c = powd(K//p)
        for i in range(2*p,K+1,p):
            c = (c-cDict[i])%MOD
        cDict[p]=c
        sum = (sum + c*p)%MOD
    print(sum)



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    solve(N, K)

if __name__ == '__main__':
    main()

Solution (Python):
Big=10**9+7
_=list(map(int,input().split(" ")))
N=_[0]
K=_[1]
gcd_list=[0 for _ in range(K)]
for i in range(K):
  s=K-i-1
  gcd_list[s]=(pow(K//(K-i), N, Big)-(sum(gcd_list[2*s+1::s+1]))%Big)%Big
answer=[(x+1)*gcd_list[x]%Big for x in range(K)]
print(sum(answer)%Big)

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, K = lr()
    MOD = pow(10, 9)+7
    lst = [0]*K
    klst = [0]*K
    for k in range(K, 0, -1):
        lst[k-1] = pow(K//k, N, MOD)
        for i in range(2, K//k+1):
            lst[k-1] -= lst[i*k-1]
        klst[k-1] = k*lst[k-1]
    print(sum(klst)%MOD)
resolve()

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

l = [0 for _ in range(K + 1)]
for i in range(1, K + 1):
  l[i] = pow(K//i, N, MOD)

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

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

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n, k = na()

def modpow(n, p, m):
    if p == 0:
        return 1
    if p % 2 == 0:
        t = modpow(n, p // 2, m)
        return t * t % m
    return n * modpow(n, p - 1, m) % m

d = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
    d[i] = modpow(k // i, n, mod)
    j = 2
    while j * i <= k:
        d[i] -= d[j * i]
        j += 1
    ans += d[i] * i % mod

print(ans % mod)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9 + 7
s = [0 for i in range(k+1)]
ret = 0

for i in range(k, 0, -1):
    p = int(k/i)
    c = pow(p, n, mod)
    for j in range(2, k+1):
        if i*j <= k:
            c -= s[i*j]
        else:
            break
    
    s[i] = c%mod

    ret = (ret + (c%mod)*i)%mod

print(ret)

Solution (Python):
MOD=10**9+7
n, k = map(int, input().strip().split())
d=[0]*(k+1)
d[0]=None

for i in range(1,k+1):
    d[i]=pow(k//i,n,MOD)


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