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 is_prime(num):
    if num == 1:
        raise ValueError("error!")
    d = 2
    while d * d <= num:
        if num % d == 0:
            return False
        d += 1
    return True
    
n, k = list(map(int, input().split()))
mod = 10 ** 9 + 7

n_power_table = [-1] * (k+1)
for i in range(k+1):
    n_power_table[i] = pow(i, n, mod)


prime_list = []
for i in range(2, k+1):
    if is_prime(i):
        prime_list.append(i)

prime_2_list = []
prime_3_list = []
prime_4_list = []
prime_5_list = []
prime_6_list = []

ll = len(prime_list)
for i, p1 in enumerate(prime_list):
    for j in range(i+1, ll):
        p2 = prime_list[j]
        if p1*p2 > k:
            break
        prime_2_list.append(p1*p2)
        for v in range(j+1, ll):
            p3 = prime_list[v]
            if p1*p2*p3 > k:
                break
            prime_3_list.append(p1*p2*p3)
            
            for w in range(v+1, ll):
                p4 = prime_list[w]
                if p1*p2*p3*p4 > k:
                    break
                prime_4_list.append(p1*p2*p3*p4)
                for x in range(w+1, ll):
                    p5 = prime_list[x]
                    if p1*p2*p3*p4*p5 > k:
                        break
                    prime_5_list.append(p1*p2*p3*p4*p5)
                    for y in range(x+1, ll):
                        p6 = prime_list[y]
                        if p1*p2*p3*p4*p5*p6 > k:
                            break
                        prime_6_list.append(p1*p2*p3*p4*p5*p6)

prime_2_list.sort()
prime_3_list.sort()
prime_4_list.sort()
prime_5_list.sort()
prime_6_list.sort()












ans = 0
temp = 0

for g in range(1, k+1):
    
    p = k // g
    
    kosuu = n_power_table[p]

    for prime in prime_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]
    
    for prime in prime_2_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]
    
    for prime in prime_3_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_4_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    for prime in prime_5_list:
        if prime > p:
            break
        kosuu -= n_power_table[p//prime]

    for prime in prime_6_list:
        if prime > p:
            break
        kosuu += n_power_table[p//prime]

    kosuu %= mod
    ans += g * kosuu
    
    temp += kosuu

print(ans% mod)

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

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

def slowsolve(N, K):
    import itertools
    import math
    data = {}
    s = 0
    KK = [i for i in range(1, K + 1)]
    for p in itertools.product(KK, repeat=N):
        cdi = p[0]
        for c in p:
            cdi = math.gcd(cdi, c)
        s += cdi
        data.setdefault(cdi, 0)
        data[cdi] += 1
    print(data)
    return s


cache = {}
def solve(N, K):
    M = pow(10, 9) + 7
    ans = 0
    for i in range(K, 0, -1):
        P = pow(K // i, N, M)
        j = i + i
        while j <= K:
            P -= cache[j]
            j += i
        while P < 0:
            P += M

        cache[i] = P
        ans += i * P
        ans %= M
    return ans

if __name__ == "__main__":
    N, K = tuple(map(int, input().split(" ")))
    print(solve(N, K))

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)
	for j in range(i*2,k+1,i):
		ans[i]-=ans[j]
print(sum(i*x for i,x in enumerate(ans))%mod)

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

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

    ctr = [0] * (K + 1)
    for g in range(K, 0, -1):
        cnt = pow(K // g, N, MOD)

        c = 2
        while c * g <= K:
            cnt = (cnt - ctr[c * g]) % MOD
            c += 1
        ctr[g] += cnt

    ans = 0
    for g, cnt in enumerate(ctr, 0):
        ans = (ans + g * cnt) % MOD

    print(ans)


if __name__ == '__main__':
    main()

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

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


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

    baisuu = [[] for _ in [0]*(k+1)]
    tree = [0]*(k+1)

    for i in range(1, k+1):
        j = 2*i
        while j <= k:
            baisuu[i] += [j]
            j += i
        tree[i] = pow(len(baisuu[i])+1, n, mod)
    for i in range(k, 0, -1):
        for j in baisuu[i]:
            tree[i] -= tree[j]
        tree[i] %= mod
    ans = 0
    for i, j in enumerate(tree):
        ans = (ans+i*j) % mod
    print(ans)


main()

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

if __name__ == '__main__':
    main()

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

count = [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):
    count[i] -= count[j]

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

print(sum_)

Solution (Python):
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
N,K=map(int,input().split())
mod=10**9+7
"""fac=[1,1]
for i in range(2,2*K+1):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]


def H(a,b):
    return(comb(a+b-1,a))
def comb(a,b):
    return(fac[a]*ifac[a-b]*ifac[b]%mod)


dp=[1 for i in range(K+1)]
for i in range(1,len(dp))[::-1]:
    n=(len(dp)-1)//i
    z=pow(n,N,mod)
    for m in range(i,len(dp),i):
        z-=dp[m]

    dp[i]+=z
    dp[i]%=mod
print(sum([dp[i]*i%mod for i in range(len(dp))])%mod)

Solution (Python):
n, k = list(map(int, input().split()))
l = [0 for i in range(k)]
ans = 0
M = 10**9 + 7











for i in range(k, 0, -1):


    b=pow(k//i, n, M)
    for j in range(i*2, k+1, i):
        b -= l[j-1]
    l[i-1] = b%M

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

print(ans%M)

Solution (Python):
from numpy import array


MOD = 10 ** 9 + 7

def solve(n, k):
    is_prime = array([True] * (k+1))
    is_prime[:2] = False
    for i in range(2, k+1):
        if i**2 > k: break
        if is_prime[i]:
            is_prime[i**2::i] = False
    primes = [i for i, _ in enumerate(is_prime) if is_prime[i]]
    
    res = [0] + [pow(k//i, n, MOD) for i in range(1, k+1)]

    for p in primes:
        for i in range(1, k//p+1):
            res[i] -= res[i*p]
            
    return sum(i*res[i] for i in range(k+1)) % MOD


def test():
    ...

if __name__ == "__main__":
    n, k = map(int, input().split())
    print(solve(n, k))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()

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

Solution (Python):
n, k = map(int, input().split())
MOD = 10**9+7
dp = [0]*(k+1)
for i in range(k, 0, -1):
    """最大値だけの場合
    例) 3 4 → gcd(4 4 4)=4
    """
    dp[i] = pow((k//i), n, MOD)
    """2*iからk+1まで差iに関して
    例) 3 4 → gcd(a, b, c)=2になるのは
    (a,b,c)=(2or4,2or4,2or4)((a,b,c)=(4,4,4)を除く)
    """
    for j in range(i+i, k+1, i):
        dp[i] -= dp[j]
ans = sum([i*dp[i] for i in range(k+1)])
ans %= MOD
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)]
for i in range(K,1,-1):
    tmp=[1]
    for j in range(2,int(pow(i+1,0.5))+1):
        if i%j==0:
            tmp.append(j)
            if i != j*j:
                tmp.append(i//j)
    for k in tmp:
        dp[k-1] -=dp[i-1]
ans = 0
for n,i in enumerate(dp):
    ans += (n+1)*i
    ans %=mod
print(ans)

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

for i in range(K,0,-1):
    x = K//i
    a = pow(x, N, mod)
    cnt = 2
    while i*cnt <= K:
        a -= dp[i*cnt]
        cnt += 1
    a %= mod
    dp[i] = a
    ans += a*i
    ans %= mod
print(ans)

Solution (Python):
import math
N, K = map(int,input().split())
MOD = 10**9 + 7
ans = 0
if K == 1:
    print(1)
else:
    ans = 0
    a = [0]*(K+1)
    for k in range(K,0,-1):
        s = K//k
        t = k*2
        u = 0
        while t <= K:
            u += a[t]
            t += k
        ans += k*(pow(s,N,MOD)-u)
        ans %= MOD
        a[k] = pow(s,N,MOD)-u
    print(ans)

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

for i in range(K,0,-1):
    x = K//i
    a = pow(x, N, mod)
    cnt = 2
    while i*cnt <= K:
        a -= dp[i*cnt]
        cnt += 1
    a %= mod
    dp[i] = a
    ans += a*i
    ans %= mod
print(ans)

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):
MOD = 10 ** 9 + 7

n, k = map(int, input().split())
x = [0 for _ in range(k + 1)]

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

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):
N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
gcd_comb = [0]*(K+1)
for i in range(K, 0, -1):
    gcd_comb[i] = pow(K // i, N, mod)
    gcd_comb[i] -= sum(gcd_comb[i + i : K + 1 :i])
    gcd_comb[i] %= mod
ans = 0
for i, n in enumerate(gcd_comb):
    if not i:
        continue
    ans = (ans + i * n) % mod
print(ans)

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

print(ans%MOD)

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):
import sys
def input(): return sys.stdin.readline().rstrip()

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

    ans = 0
    memo = [0] * (K+1)
    def getLarge(x):
        if x == 1:
            return sum(memo)
        else:
            return sum(memo[x::x])

    for i in range(K, 0, -1):
        Ki = K // i
        c = pow(Ki, N, MOD) - getLarge(i) % MOD
        memo[i] = c
        ans += i * c
        ans %= MOD
    print(ans % MOD)

if __name__ == '__main__':
    main()

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

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

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)

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

n, k = map(int, input().split())
gcd_dp = [0] * (k + 1)

for i in range(k, 0, -1):
    gcd_dp[i] = pow(k // i, n, Mod)
    a = 2
    while i * a <= k:
        gcd_dp[i] -= gcd_dp[i * a]
        a += 1

ret = 0
for i in range(k + 1):
    ret += (i % Mod) * (gcd_dp[i] % Mod)
    ret %= Mod
print(ret)

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

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

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)

Solution (Python):
import numpy as np
n, k = map(int, input().split())
MOD = 10**9+7
dp = np.zeros(k+1, dtype=np.int64)
for i in range(k, 0, -1):
  dp[i] = pow((k//i), n, MOD)
  dp[i] -= dp[i+i::i].sum()
j = np.arange(k+1)
ans = (j*dp).sum() % MOD
print(ans)

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

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

print(sum(i*j%mod for i, j in enumerate(num))% mod)

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

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)


def gcd_list(numbers):
    return reduce(gcd, numbers)

def euler_phi(n):
    phi = n
    for i in set(prime_factorize(n)):
        phi *= (1 - (1 / i))
    return int(phi)

def prime_factorize(n):
    
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, k = map(int, input().split())
MOD = 10**9 + 7
flt = FLT(MOD)
memo = [-1 for _ in range(k+1)]
ans = 0
for i in range(1, k+1):
    d = k // i
    ans += flt.rep_sqr(d, n) * euler_phi(i)
print(ans % MOD)

Solution (Python):


import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)

def is_prime(n):
	for i in range(2, int(-(-n**0.5//1))+1):
		if n % i == 0:
			return False
	return True

def comb(n, r):
	return fact(n) // fact(n-r) // fact(r)

fact_memo = [1, 1]
def fact(n):
	if len(fact_memo) > n:
		return fact_memo[n]
	else:
		for i in range(len(fact_memo), n+1):
			fact_memo.append(fact_memo[i-1] * i)
		return fact_memo[n]


def main():
	log = Logger(1)
	n, k = map(int, sys.stdin.readline().split())
	ans = 0
	mod = 10 ** 9 + 7
	a = [0]*(k+1)
	for i in range(1, k+1):
		a[i-1] = pow(k//i, n, mod)
	ans = 0
	for i in list(range(1, k+1))[::-1]:
		for j in range(1, k//i):
			a[i-1] -= a[i-1 + i * j]
		ans += a[i-1] * i
		ans %= mod
	print(ans)



main()

Solution (Python):
import sys
from collections import *
import heapq
import math
from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
ans=0
lst=[0]*(k+1)
for i in range(k):
    tori=k//(k-i)
    lst[k-i]=pow(tori,n,mod)
    for j in range(1,tori):
        lst[k-i]-=lst[(k-i)*(j+1)]

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

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

class FLT:
    def __init__(self, mod=10**9+7):
        self.mod = mod

    def rep_sqr(self, base, k):
        ans = 1
        while k > 0:
            if k & 1:
                ans = ans * base % self.mod
            base = base * base % self.mod
            k >>= 1
        return ans

    def inv(self, a):
        """ 逆元を取る """
        return self.rep_sqr(a, self.mod-2)


def gcd_list(numbers):
    return reduce(gcd, numbers)

def euler_phi(n):
    phi = n
    for i in set(prime_factorize(n)):
        phi *= (1 - (1 / i))
    return int(phi)

def prime_factorize(n):
    
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n, k = map(int, input().split())
MOD = 10**9 + 7
flt = FLT(MOD)
memo = [-1 for _ in range(k+1)]
ans = 0
for i in range(1, k+1):
    d = k // i
    if memo[d] == -1:
        memo[d] = flt.rep_sqr(d, n)
    ans += memo[d] * euler_phi(i)
print(ans % MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]


class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,k=MI()
    dp=[mint(0) for _ in range(k+1)]
    for a in range(k,0,-1):
        dp[a]+=pow(k//a,n,md)
        for b in range(2*a,k+1,a):
            dp[a]-=dp[b]
    ans=0
    for a in range(1,k+1):
        ans+=dp[a]*a
    print(ans)

main()

Solution (Python):
n, k = map(int, input().split())
MOD = 10**9+7
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 = sum([i*dp[i] for i in range(k+1)])
ans %= MOD
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]


class mint:
    def __init__(self, x):
        self.__x = x % md

    def __str__(self):
        return str(self.__x)

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10**9+7

def main():
    n,k=MI()
    dp=[mint(0) for _ in range(k+1)]
    for a in range(k,0,-1):
        dp[a]+=pow(k//a,n,md)
        for b in range(2*a,k+1,a):
            dp[a]-=dp[b]
    ans=0
    for a in range(1,k+1):
        ans+=dp[a]*a
    print(ans)

main()

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

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

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

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()
    if k == 2:
        print((pow(2,n,mod)+1)%mod)
    elif k == 3:
        print((pow(3,n,mod)+3)%mod)
    elif k == 4:
        print((pow(4,n,mod)+pow(2,n,mod)+4)%mod)
    elif k == 5:
        print((pow(5,n,mod)+pow(2,n,mod)+8)%mod)
    else:
        f = [-1]*(k+1)
        p = 2
        while p <= k:
            x = 2*p
            while x <= k:
                f[x] -= f[p]
                x += p
            p += 1
        ans = 0
        p = [1]
        for i in range(1,k+1):
            p.append(pow(k//i,n,mod))
        for i in range(1,k+1):
            res = p[i]
            x = 2*i
            j = 2
            while x <= k:
                res += p[x]*f[j]
                x += i
                j += 1
            ans += i*res
            ans %= mod
        print(ans)
    return


if __name__ == "__main__":
    solve()

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

def Eratosthenes(N):
    """
    Eratosthenesの篩: N以下の素数のリストを返す
    """
    N+=1
    is_prime_lst = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_lst[i]:
            is_prime_lst[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_lst[i]]

def bpm(m,n,mod):
    """
    Bisection power method : 二分累乗法
    """
    if n==0:
        return 1
    elif n%2:
        k=bpm(m,n//2,mod)
        return k*k*m%mod
    else:
        k=bpm(m,n//2,mod)
        return k*k%mod

def main():
    N,K=map(int,input().split())
    Primes=Eratosthenes(K)
    tmp=[0]+[bpm(K//i,N,MOD) for i in range(1,K+1)]
    for p in Primes:
        for j in range(p,K+1,p):
            tmp[j//p] -= tmp[j]
    print(sum(a*b for a,b in enumerate(tmp))%MOD)

main()

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


def solve(n, k):
    
    is_prime = [1] * (k + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    for p in range(2, k + 1):
        if p * p > k:
            break
        if is_prime[p]:
            for q in range(p * p, k + 1, p):
                is_prime[q] = 0
    primes = [p for p in range(k + 1) if is_prime[p]]

    res_arr = [0] + [pow(k // i, n, MOD) for i in range(1, k + 1)]
    
    for p in primes:
        for i in range(1, k // p + 1):
            res_arr[i] -= res_arr[i * p]
    
    res = sum([i * res_arr[i] for i in range(k + 1)]) % MOD
    
    return res


def main():
    n, k = map(int, input().split())
    res = solve(n, k)
    print(res)


def test():
    assert solve(3, 2) == 9
    assert solve(3, 200) == 10813692
    


if __name__ == "__main__":
    test()
    main()

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

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

n,k = LI()
f = [-1]*(k+1)
p = 2
while p <= k:
    x = 2*p
    while x <= k:
        f[x] -= f[p]
        x += p
    p += 1
ans = 0
p = [1]
for i in range(1,k+1):
    p.append(pow(k//i,n,mod))
for i in range(1,k+1):
    res = p[i]
    x = 2*i
    j = 2
    while x <= k:
        res += p[x]*f[j]
        x += i
        j += 1
    ans += i*res
    ans %= mod
print(ans%mod)

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
    while p <= k:
        x = 2*p
        while x <= k:
            f[x] -= f[p]
            x += p
        p += 1
    ans = 0
    p = [1]
    for i in range(1,k+1):
        p.append(pow(k//i,n,mod))
    for i in range(1,k+1):
        res = p[i]
        x = 2*i
        j = 2
        while x <= k:
            res += p[x]*f[j]
            x += i
            j += 1
        ans += i*res
        ans %= mod
    print(ans%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import bisect
import copy
import heapq
import sys
import itertools
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N, K = read_values()
    C = [0] * (K + 1)

    for M in range(K, 1, -1):
        c = K // M
        C[M] = pow(c, N, mod)
        for r in range(2 * M, K + 1, M):
            C[M] -= C[r]
            C[M] %= mod

    C[1] = pow(K, N, mod) - sum(C) % mod
    C[1] %= mod
    print(sum(i * k for i, k in enumerate(C)) % mod) 


if __name__ == "__main__":
    main()

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 = (ans + b[i]) % mod

print(ans)

Solution (Python):
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N,K = Ints()

mod = 10**9+7

One = [1,1]
R = 1

def divisor(M):
    A = []
    for i in range(1,int(M**0.5)+1):
        if M%i == 0:
            A.append(i)
            if M//i !=  i:
                A.append(M//i)
    
    return A

for i in range(2,K+1):
    tmp = 0
    tmp += pow(i,N,mod)
    tmp -= pow(i-1,N,mod)
    
    for j in divisor(i):
        if j!=i:
            tmp -= One[j]
    
    
    One.append(tmp%mod)

ans = 0
Rone = [0]
for i in range(1,K+1):
    Rone.append((Rone[-1]+One[i])%mod)


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