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):
N, K = list(map(int,input().split()))

mod = 10**9 + 7
array = []

for k in range(1, K+1):
    array.append(pow((K // k), N, mod))
    
for k in range(K, 0, -1):
    for i in range(2*k, K+1, k):
        array[k-1] -= array[i-1]

sum = 0
for k in range(1, K+1):
    array[k-1] *= k
    array[k-1] %= mod
    sum += array[k-1]
    
sum %= mod

print(sum)

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

n, k = map(int, input().split())
otv = 0
D = [0] * (k + 1)
for i in range(1, k + 1):
    D[i] = pow(k // i, n, mod)

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

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

print(otv)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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[i] - D[j]) % mod

    res = 0
    for i in range(1, k + 1):
        res = (res + D[i] * i) % mod

    print(res)


if __name__ == '__main__':
    resolve()

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())

MOD = 10 ** 9 + 7


just = [0] * (K + 1)

for X in range(K, 0, -1):
    just[X] = pow(K // X, N, MOD)
    
    mul = X + X
    while mul <= K:
        just[X] -= just[mul]
        mul += X

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

print(ans)

Solution (Python):
n,k=map(int,input().split())
mod=10**9+7
bk = [pow((k//l),n,mod) for l in range(1,k+1)]

BK=[0]*(k+1)
for i in range(k,0,-1):
    hiku=0
    for j in range(k//i+1):
        if j*i>k:
            break
        hiku+=BK[i*j]
    BK[i] = bk[i-1]-hiku

ans=0
for i,bb in enumerate(BK):

    ans=ans+i*bb %mod
print(ans%mod)

Solution (Python):

import sys

MOD = 1000000007  

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

def solve(N: int, K: int):
    ans = 0

    x = [1] * (K+1)

    for i in range(K, 0, -1):
        if i * 2 <= K:
            x[i] = modpow(K//i, N)
            j = 2
            while i * j <= K:
                x[i] -= x[i*j]
                j += 1
            ans += x[i] * i % MOD
        else:
            ans += i
    print(ans%MOD)


    return



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):
N,K = map(int,input().split())
mod = 10**9+7
ans = [0]*(K+1)
result = 0

for i in range(K,0,-1):
    c = K//i
    ans[i] += pow(c,N,mod)
    for j in range(i,K+1,i):
        if i != j:
            ans[i] -= ans[j]
    result += i*ans[i] % mod

print(result%mod)

Solution (Python):
import sys, math
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

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

    """
    gcd(a1,...,aN) = dになる時を考える。もしこの個数がわかれば\sum_dして答えを得る。
    （決め打ち二分探索的な発想として出てくるのか？？？）
    これはa1,...,aNがすべてdの倍数のときと予想が立つが、すぐにgcd=2d, 3d,...の場合もありうると気づく。
    しかしこの考察から
            gcd(a1,...,aN)がdの倍数になる(a1,...,aN)の個数 = (K // d)^N
    という式を得る。

    同様にgcd(a1,...,aN)=(2dの倍数), gcd(a1,...,aN)=(3dの倍数)なる(a1,...aN)の個数もすぐ求まるので、
    kd <= Nなるなるべく大きなkを考えて（そうするとgcd(a1,...,aN)=mdなる(a1,...aN)の個数がばっちり求まる）、
    あとはkを小さくしていきながら適当な引き算を施すことで答えが求まる。
    """

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

if __name__ == "__main__":
    main()

Solution (Python):
def make_divisors(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)
    return divisors

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

lst = [0 for i in range(k+1)]
for i in range(1, k+1)[::-1]:
    num = pow(k//i, n, mod)
    lst[i] += num
    divisors = make_divisors(i)
    for j in divisors:
        if j != i: lst[j] -= lst[i]

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

Solution (Python):
MOD = int(1e9+7)


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


if __name__ == "__main__":
    main()

Solution (Python):

N, K = list(map(int, input().split()))
mod = 10 ** 9 + 7
sum = 0
count = [0 for _ in range(K+1)]
pows = [0 for _ in range(K+1)]

def cal_pow(k, pows):
    if pows[k] == 0:
        pows[k] = pow(k,N, mod)
        return pows[k]
    else:
        return pows[k]

for h in range(K):
    k = K-h
    sub, alpha = 0,2
    while True:
        if alpha*k <= K:
            sub += count[alpha*k]
            alpha += 1
        else:break
    count[k] = (cal_pow(K//k, pows) - sub) % mod

for k, c in enumerate(count):
    sum += k * c % mod
print(sum % mod)

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

count = [0] * (K+1)
ans = 0
for now in range(K, 0, -1):
    count[now] = pow(K // now, N, MOD)
    for j in range(2*now ,K+1, now):
        count[now] -= count[j]
        if count[now] < 0:
            count[now] += MOD
    ans += now * count[now]
print(ans % MOD)

Solution (Python):
MOD = 1000000007
def fast_power(base, power):
    """
    Returns the result of a^b i.e. a**b
    We assume that a >= 1 and b >= 0

    Remember two things!
     - Divide power by 2 and multiply base to itself (if the power is even)
     - Decrement power by 1 to make it even and then follow the first step
    """

    result = 1
    while power > 0:
        
        if power % 2 == 1:
            result = (result * base) % MOD

        
        power = power // 2
        
        base = (base * base) % MOD

    return result
n,k = [int(j) for j in input().split()]
d = dict()
ans = k
d[k] = 1
sum_so_far = 1
for i in range(k-1, 0, -1):
	d[i] = fast_power(k//(i),n)
	for mul in range(i*2, k+1, i):
		d[i]-=d[mul]
	
	ans+=(i*d[i])%MOD
	
		
print(ans%MOD)

Solution (Python):
n,k = [int(x) for x in input().split()]
li = [0]*(k+1)
mod = 10**9+7

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

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

for i in range(K, 0, -1):
    n = pow((K//i), N, mod)
    for x in range(i, K+1, i):
        n -= gcd_l[K-x]
    gcd_l[K-i] = n%mod

res = 0
for i in range(K):
    res += (gcd_l[i] * (K-i))%mod

print(res%mod)

Solution (Python):
from functools import reduce

MOD = 10**9 + 7
N, K = map(int, input().split())
cnt = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    temp = cnt[2*k::k]
    cnt[k] = pow(K // k, N, MOD) - (reduce(lambda x, y: (x + y) % MOD, temp) if temp else 0)
    ans += (cnt[k] * k) % MOD; ans %= MOD
print(ans)

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

for i in range(K, 0, -1):
  
  ans2 = pow((K // i), N, MOD)
  x = i
  while x <= K:
    ans2 -= gcd_list[K - x]
    x += i
  gcd_list[K - i] = ans2 % MOD
  
ans = 0  
for i in range(K):
  ans += (gcd_list[i] * (K - 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):
	a = int(k/i)
	c = pow(a,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

def Pow(a, n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

N, K = map(int, input().split())
li = [0] * (K+1)
for i in range(K, 0, -1): 
    li[i] = Pow((K//i), N)
    for j in range(2,K//i+1):
        li[i] = (li[i] - li[i*j])%mod
ans = 0
for i in range(1, K+1):
    ans = (ans + i*li[i])%mod
print(ans)

Solution (Python):


def pow(N,R,mod):
    ans = 1
    i = 0
    while((R>>i)>0):
        if (R>>i)&1:
            ans *= N
            ans %= mod
        N = (N*N)%mod
        i += 1
    return ans%mod


def main():
    N,K = map(int,input().split())
    li = [0 for _ in range(K)]

    mod = 10**9+7
    ans = 0
    for i in range(K,0,-1):
        mm = K//i
        mm = pow(mm,N,mod)

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


        ans += (i*mm)%mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


def pow(N,R,mod):
    ans = 1
    i = 0
    while((R>>i)>0):
        if (R>>i)&1:
            ans *= N
            ans %= mod
        N = (N*N)%mod
        i += 1
    return ans%mod


def main():
    N,K = map(int,input().split())
    li = [0 for _ in range(K)]

    mod = 10**9+7
    ans = 0
    for i in range(K,0,-1):
        mm = K//i
        mm = pow(mm,N,mod)

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


        ans += (i*mm)%mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

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())

history = [0] * (K + 1)
total = 0

divide = pow(10, 9) + 7

for i in range(K, 0, -1):
  history[i] = pow(K//i, N, divide)
  for j in range(2, K//i + 1):
    history[i] -= history[i * j]
  total += ((i * history[i]) % divide)
  
total = total % divide
print(total)

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

print(ans)

Solution (Python):
N,K = list(map(int,input().split()))
mod = int(1e9+7)
d = dict()
ans = 0
for X in range(K,0,-1):
  res = pow(K//X,N,mod)
  for k in range(2*X,K+1,X):
    res -= d[k]
  d[X] = res%mod
  ans += (res*X)%mod
  
print(ans%mod)

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

a = [0] *(k+1)

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

for x in range(k, 0, -1):
    for i in range(2, k // x + 1):
        a[x] -= a[x * i]

answer = sum([i * x for i,x in enumerate(a)])

print(answer % MOD)

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

dp = [0 for _ in range(K + 1)]
res = 0

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

print(res)

Solution (Python):


def pow(N,R,mod):
    ans = 1
    i = 0
    while((R>>i)>0):
        if (R>>i)&1:
            ans *= N
            ans %= mod
        N = (N*N)%mod
        i += 1
    return ans%mod


def main():
    N,K = map(int,input().split())
    li = [0 for _ in range(K)]

    mod = 10**9+7
    ans = 0
    for i in range(K,0,-1):
        mm = K//i
        mm = pow(mm,N,mod)

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


        ans += (i*mm)%mod
        ans %= mod

    print(ans)

if __name__ == '__main__':
    main()

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

mod = 10 ** 9 + 7

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x % mod
        x = x * x % mod
        n //= 2

    return K * x % mod


memo = {}
ans = 0

for x in reversed(range(1, k + 1)):
    memox = pow_k((k // x), n)
    for i in range(2, k // x + 1):
        memox -= memo[i * x]
        memox %= mod
    memo[x] = memox
    ans += x * memox % mod
    ans %= mod

print(ans)

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

Solution (Python):


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    mod = 10**9 + 7

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

if __name__ == '__main__':
    main()

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

def modpow(a, n, mod):
    ans = 1
    while n > 0:
        if n&1:
            ans = ans * a % mod
        a = a * a % mod
        n = n >> 1
    return ans
for x in range(K,0, -1):
    a = int((K // x) % mod)
    b = modpow(a, N, mod)
    for i in range(2, K//x +1):
        b = (b - lis[x*i-1]) %mod
        if b < 0:
            b += mod
    lis[x-1] = b
    ans = (ans + b*x%mod) % mod
print(int(ans))

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

a = [1] * (k+1)
b = [ i for i in range(k+1) ]

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

ans = 0
for i in range(1,k+1):
  ans += b[i]
  if ans >= mod:
    ans %= mod

print(ans)

Solution (Python):
n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % MOD
print(t)

Solution (Python):
n, k = (int(x) for x in input().split())
c = {} 
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
    q = k // x
    c[x] = pow(q, n, MOD) - sum(c[x * y] for y in range(2, q + 1))
    t += c[x] * x
    t = t % 1000000007
print(t)

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

MOD = 10 ** 9 + 7

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

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

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

MOD = 10 ** 9 + 7

cache = {1: 1}
def f(k, n):
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
    result %= MOD
print(result)

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

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

A = [0] + [pow(K // x, N, mod) for x in range(1, K + 1)]
for x in reversed(range(1, K + 1)):
    for i in range(2, K // x + 1):
        A[x] -= A[i * x]

print(sum(i * a for i, a in enumerate(A)) % mod)

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
print(result % MOD)

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


print(sum(f(K // i, N) * i for i in range(1, K + 1)) % MOD)

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result


result = 0
for i in range(1, K + 1):
    result += f(K // i, N) * i
    result %= MOD
print(result)

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

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

MOD = 10 ** 9 + 7

cache = {}
def f(k, n):
    if k == 1:
        return 1
    if k in cache:
        return cache[k]
    result = pow(k, n, MOD)
    for i in range(2, k + 1):
        result -= f(k // i, n)
        result %= MOD
    cache[k] = result
    return result

result = 0
for i in range(2, K + 1):
    result += f(K // i, N) * i
result += f(K, N)
result %= MOD
print(result)

Solution (Python):
import math

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

cnt = [0]*(k+1)

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

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

ans = 0

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

print(ans)

Solution (Python):
import math

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

cnt = [0]*(k+1)

for i in range(1, k+1):
    cnt[i] = pow(math.floor(k/i), n, mod)

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

ans = 0

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

print(ans)

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

gcd = {}
s = 0

for x in range(K,0,-1):
  
    i = K // x
    tmp = pow(i,N,mod)  
    
    if i > 1:
        for j in range(2,i+1):
            tmp -= gcd[j * x]
    
    gcd[x] = tmp
    s += (tmp * x) % mod
    s %= mod

print(s)

Solution (Python):
import sys







import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


mod = 1000000007

def gcd(nums):
    return functools.reduce(euclid, nums)

def euclid(a, b):
    if b > a:
        a, b = b, a
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

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

    ans = 0
    count = [0] * K
    for X in range(K,0,-1):
        
        tmp = pow(K//X, N, mod)
        diff = count[X-1::X][1:]
        if len(diff) != 0:
            tmp = (tmp - sum(diff)) % mod
        count[X-1] = tmp

    ans = sum([((x+1)*count[x])%mod for x in range(K)])%mod
    
    

    
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

gcd = {}
s = 0

for x in range(K,0,-1):
  
    i = K // x
    tmp = pow(i,N,mod)  
    
    if i > 1:
        for j in range(2,i+1):
            tmp -= gcd[j * x]
    
    gcd[x] = tmp
    s += (tmp * x) % mod
    s %= mod

print(s)

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

A = list(0 for _ in range(K + 1))
B = list(0 for _ in range(K + 1))

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

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

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

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

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

MOD = 10**9+7
arr = [pow(K//i, N, MOD) for i in range(1,K+1)]

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

print(sum(arr)%MOD)

Solution (Python):

"""
問題を「1~kまでの数字を用いた長さnの数列において、gcdがDになる数列はいくつあるか」
というふうに置き換える。(1<=D<=k)
更に制約を替えて、gcdが"Dの倍数"(但し,k以下)でも良いのでそれを全て求めよ、
というふうになった場合、全ての要素はD*n(nは整数,D*n<=k)となる。
この制約によって、そのような数列の数は(k/D)^nとして表せる。(これが大事)
例：
n = 3,k = 4の場合で、D(gcd)=2について求める
(4//2)**3 = 8※

そこで、大きい方からgcdがDになる数列の個数(これをメモ化)を求めていった場合、
Dの倍数がk以下であるならば、予めメモしておいたその値分を引いてやる。
これによって全ての通り数が求まる。
例の続き:
D=2について、D*n <= k という制約のもとでn=2が存在する。
D = 2*2 = 4の時の通り数は、4,4,4の1通り※なので、
D(gcd)=2となるパターン数は、※より、
8-1=7 となる。
(この7通りは2と4からなる数列で、全ての値が4になる場合を引いている)
"""
import sys
readline = sys.stdin.buffer.readline
n,k = map(int,readline().split())
mod = 10**9+7

ans = 0
count = [0]*(k+1)
for D in range(k,0,-1):
    mul = k//D 
    res = pow(mul,n,mod)
    for i in range(2,mul+1):
        res -= count[i*D]
    count[D] = res 
    ans += res*D 
    ans %= mod

print(ans)

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

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

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

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

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

g = [0 for _ in range(k)]
for i in range(k,0,-1):
  g[i-1] = pow(k//i,n,MOD)
  
  
  for j in range(2,k+1):
    if i*j > k:
      break
    g[i-1] -= g[i*j-1]
    g[i-1] %= MOD

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

Solution (Python):
mod=10**9+7
n,k= map(int, input().split())
x=[0]*(k+1)
y=0


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

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

print(ans)

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

cnt = [0] * (K + 1) 
for x in range(1, K + 1):
    cnt[x] = pow(K // x, N, MOD)
for x in range(K, 0, -1): 
    for i in range(2, K // x + 1):
        cnt[x] -= cnt[x * i]
ans = 0
for k in range(K+1):
    ans += cnt[k] * k
ans = ans % MOD
print(ans)

Solution (Python):
N,K = map(int,input().split())
res = [0]*(K+1)
ans = 0
MOD = 10**9+7
def make_divisors(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)
    return divisors

for k in range(K,0,-1):
    y = make_divisors(k)
    s = K//k
    tmp = pow(s, N, MOD)
    val = tmp-res[k]
    ans += k*val
    for yy in y:
        res[yy] += val
print(ans%MOD)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	
	k, n = IN()
	
	bb=[0]*n
	for i in range(n,0,-1):
		pattern = pow((n//i), k, mod)
		for b in range(2, n+1):
			if (i * b)-1 >= n:
				break
			pattern -= bb[(i*b)-1]
			pattern %= mod
		bb[i-1]=pattern
	ret=0
	
	for i, v in enumerate(bb):
		ret += v*(i+1)
		ret %=mod
	return ret
		
		
		
	
	
	ret=pow(b,c,mod)
	print(ret)
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

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

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

def pow_mod(a, n):
    if n == 1:
        return a
    half = pow_mod(a, n // 2)
    if n % 2 == 1:
        ret = half * a % MOD
        ret = ret * half % MOD
    else:
        ret = half * half % MOD
    return ret

ans_dict = dict()
for g in range(k, 0, -1):
    ans_dict[g] = pow_mod(k // g, n)
    for i in range(2, k + 1):
        if g * i <= k:
            ans_dict[g] -= ans_dict[g * i]
            if ans_dict[g] < 0:
                ans_dict[g] += MOD
            elif ans_dict[g] > g:
                ans_dict[g] -= MOD
        else:
            break

ans = 0
for g, v in ans_dict.items():
    ans += g * v
    ans %= MOD

print(ans)

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

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


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


def main():
  n,k=LI()
  ans=[0]*(k+1)
  for i in range(1,k+1)[::-1]:
    x=powMod((k//i),n,mod)
    for j in range(2,k//i+1):
      x-=ans[i*j]
    x%=mod
    ans[i]=x

  ret=0
  
  for i,x in enumerate(ans):
    ret+=x*i
    ret%=mod
  return ret


print(main())

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

cnt = [0] * (k + 1)
for num in range(1, k + 1):
    cnt[num] = pow((k // num), n, MOD)

for num in range(1, k + 1)[::-1]:
    for i in range(2, k // num + 1):
        cnt[num] -= cnt[num * i]
        cnt[num] % MOD

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

Solution (Python):








import math
from functools import reduce
import sys
sys.setrecursionlimit(15000)

n,k = map(int,sys.stdin.readline().split())
dp = [0]*(k+1)
s = 0

l = 0
for x in range(1,k+1)[::-1]:
    dp[x] = pow(k//x,n,1000000007)
    j = 2
    
    for j in range(2*x,k+1,x):
        
        dp[x] -= dp[j]
    s = (s + (dp[x]*x))%1000000007




print(s)

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

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

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

print(ans%MOD)

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

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

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

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

Solution (Python):


n,k = map(int, input().split( ))
memo = [-1]*(k+1)
mod = 10**9+7
def rec(x):
    if memo[x]>=0:
        return memo[x]
    mult = 0
    for i in range(x*2,k+1,x):
        mult += rec(i)
    res = memo[x] = pow(k//x,n,mod) - mult
    return res
ans = 0
rec(1)
for i in range(1,k+1):
    ans += i*memo[i]
print(ans%mod)

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

ans = 0

"""
dp[i] =　gdc がi となる場合のgcdの総和
"""
dp = [0] * (k+100)
for i in range(k, 0, -1):
    dp[i] = pow(k//i, n, MODINT)
    for j in range(i*2, k+1, i):
        dp[i] -= dp[j]
    ans += (dp[i]*i)%MODINT
print(ans%MODINT)

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, K: int):
    counts = [0] * (K+1)
    for i in range(K, 0, -1):
        c = pow(K//i, N, MOD)
        for j in range(i+i, K+1, i):
            c -= counts[j]
        counts[i] = c
    ans = 0
    for i, c in enumerate(counts):
        ans = (ans + (i * c) % MOD) % MOD
    print(ans)



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):
n, k = list(map(int, input().split()))
mod = int(1e9 + 7)

q = [0] * (k + 1)
for i in range(1, k+1)[::-1]:
    q[i] = pow(k//i, n, mod)
    for j in range(2, k // i + 1):
        if i * j > k:
            continue
        q[i] -= q[i * j]
s = 0
for i, qq in enumerate(q):
    s += i * qq
    s %= mod
print(s)

Solution (Python):
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    r = 0
    D = [0] * (K + 1)
    for i in reversed(range(1, K + 1)):
        D[i] = pow(K // i, N, mod) - sum(D[::i])
    return sum(i * j for i, j in enumerate(D)) % mod

print(main())