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):
import sys
mod = 7 + 10 ** 9

def solve():
    N, K = map(int,input().split())
    count = [0] * (K + 1)
    ans = 0
    for i in reversed(range(1, K + 1)):
        upper = K // i
        count[i] += pow(upper, N, mod)
        count[i] %= mod
        ans += (count[i] * i) % mod
        ans %= mod
        for j in range(2, i + 1):
            if j ** 2 > i: break
            if i % j == 0:
                count[j] += (mod - count[i])
                count[j] %= mod
                if j ** 2 != i:
                    count[i // j] += (mod - count[i])
                    count[i // j] %= mod
        count[1] += (mod - count[i])
        count[1] %= mod
    print(ans)
        
    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def solve(n, k):
    if k == 1:
        return 1

    MOD = 10 ** 9 + 7

    ans = (k // 2 + 1 + k) * (k - k // 2) // 2 % MOD  
    cnt = {1: 1}

    def get(d):
        if d in cnt:
            return cnt[d]
        result = pow(d, n, MOD)
        result -= d - d // 2
        for i in range(2, d // 2 + 1):
            result -= get(d // i)
        result %= MOD
        cnt[d] = result
        return result

    for i in range(1, k // 2 + 1):
        ans += i * get(k // i)
        ans %= MOD

    return ans


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

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

MOD = 10 ** 9 + 7

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

    ni = i + i
    while ni <= K:
        c -= CNT[ni]
        ni += i

    ans += c * i
    ans %= MOD
    num += c
    CNT[i] = c

rest = pow(K, N, MOD)
ans += rest - num
ans %= MOD

print(ans)

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

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

def func(n):
    r = n
    for i in range(2, n + 1):
        if i ** 2 > n:
            break

        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        
    if n > 1:
        r -= r // n
    return r


MOD = 10 ** 9 + 7
ans = 0
for i in range(1, K + 1):
    ans += func(i) * pow(K // i, N, MOD)
print(ans % MOD)

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

def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


N, K = map(int, input().split())
tot = [0]*(K+1)

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

print(ans%MOD)

Solution (Python):
def divisors(n):
    res = []
    for d in range(1, int(n**0.5)+1):
        if n%d==0:
            res.append(d)
            res.append(n//d)
    res = sorted(set(res))
    return res


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N, K = map(int, input().split())
invK = modinv(K)
P = [0] * (K+1)
mod = 10**9+7
for i in range(1, K+1):
    p = pow(K//i * invK, N, mod)
    P[i] = p
KN = pow(K, N, mod)
ans = 0



for i in range(K, 1, -1):
    
    for d in divisors(i):
        if d!=i:
            P[d] -= P[i]
for i, p in enumerate(P[1:], 1):
    n = p * KN % mod
    
    ans = (ans + n * i) % mod
print(ans)

Solution (Python):
def fac(n):
    global f
    rtn = {}
    while 1 < n:
        p = n // f[n]
        if p in rtn:
            rtn[p] += 1
        else:
            rtn[p] = 1
        if f[n] == 1:
            break
        n //= p
    return rtn

def div(n):
    dic = fac(n)
    rtn = [1]
    for k, v in dic.items():
        l = len(rtn)
        for i in range(l):
            for j in range(1, v + 1):
                rtn.append(rtn[i] * k**j)
    return rtn

n, k = map(int, input().split())
m = int(1e9 + 7)
f = [1 for _ in range(100001)]
for i in range(2, 100001):
    if f[i] == 1:
        for j in range(2, 100000 // i + 1):
            if f[i * j] == 1:
                f[i * j] = j

cnt = [0 for _ in range(k + 1)]
for i in range(k, 0, -1):
    cnt[i] += pow(k // i, n, m)
    ds = div(i)
    for d in div(i)[:-1]:
        cnt[d] -= cnt[i]
        cnt[d] %= m
for i in range(2, k + 1):
    cnt[i] *= i
    cnt[i] %= m
ans = sum(cnt) % m
print(ans)

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


def pow_mod(x, n, mod):
    if n > 1:
        return pow_mod(pow(x,2) % mod, n//2, mod) * pow(x, n%2) % mod
    else:
        return x


pow_n = [-1] * (k+1)
for i in range(1,k+1):
    if pow_n[k//i] == -1:
        pow_n[k//i] = pow_mod(k//i, n, mod)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 10**9 + 7
N, K = map(int, read().split())

is_prime = np.zeros(K + 10, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, K + 10, 2):
    if p * p > K:
        break
    if is_prime[p]:
        is_prime[p * p:: p + p] = 0
primes = np.where(is_prime)[0]


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

for p in primes.tolist():
    for i in range(K // p + 1):
        A[i] -= A[i * p]

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

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


def phi(n):
    r = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            r -= r // i
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        r -= r // n
    return r


n, k = map(int, input().split())
ans = 0
for i in range(1, k + 1):
    ans += phi(i) * pow(k // i, n, MOD)
print(ans % MOD)

Solution (Python):
def divisors(n):
    res = []
    for d in range(1, int(n**0.5)+1):
        if n%d==0:
            res.append(d)
            res.append(n//d)
    res = sorted(set(res))
    return res


def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

N, K = map(int, input().split())
invK = modinv(K)
P = [0] * (K+1)
mod = 10**9+7
for i in range(1, K+1):
    p = pow(K//i * invK, N, mod)
    P[i] = p
KN = pow(K, N, mod)
ans = 0



for i in range(K, 1, -1):
    
    for d in divisors(i):
        if d!=i:
            P[d] -= P[i]
for i, p in enumerate(P[1:], 1):
    n = p * KN % mod
    
    ans = (ans + n * i) % mod
print(ans)

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

class E :
    def __init__ (self) :
        self.MOD = int(1e9+7)

    def e(self, n, k) :
        if k == 1 :
            return (n*(n+1))//2 
        
        ans = 0

        dp = dict()
        for i in range(1, n+1) :
            dp[i] = pow( n//i, k, self.MOD)

        for i in range(1, n+1)[::-1] :
            for j in range(i+i,n+1,i) :
                dp[i] -= dp[j]
            
        for i in range(1, n+1) : 
            ans = (ans + dp[i]*i) % self.MOD
        
        return ans

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def gcd(a, b):
    
    while b > 0:
        a, b = b, a % b

    return a


MOD = 10**9 + 7


def POW(a, p):
    if a == 1 or p == 0:
        return 1

    if p == 1:
        return a
    else:
        return (POW(a, p // 2)**2 * (a**(p % 2))) % MOD


def ShinKosuu(k, kosuu, shinkosuu):
    ret = kosuu[k]
    for t in range(k * 2, K + 1, k):
        ret -= shinkosuu[t]
    return ret


def main():

    ans = 0
    kosuu = [0] * (K + 1)
    shinkosuu = [0] * (K + 1)
    for k in range(K, 0, -1):
        kosuu[k] = POW(K // k, N)
        shinkosuu[k] = ShinKosuu(k, kosuu, shinkosuu)
        ans = (ans + k * shinkosuu[k]) % MOD
    

    print(ans)


if __name__ == '__main__':
    N, K = inpl()
    main()

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

from functools import lru_cache

@lru_cache()
def pow(N,K):
    if K==0:
        return 1
    elif K==1:
        return N
    if K%2==0:
        return (pow(N,K//2)*pow(N,K//2))%mod
    else:
        return (N*pow(N,K-1))%mod



def f(N,K,i):
    if table[K]>0 and i==1:
        return table[K]

    if K==i:
        return 1
    elif K==1:
        return 1

    if i==1:
        sigma=0
        for j in range(2,K+1):
            sigma+=f(N,K//j,1)
            sigma=sigma%mod
        retval=(pow(K,N)-sigma)%mod
        table[K]=retval
        return retval

    else:
        return f(N,K//i,1)%mod


def calc(N,K):
    retval=0
    for i in range(1,K+1):
        retval+=i*f(N,K,i)
        retval=retval%mod
    return retval

N,K=[int(i) for i in input().split(" ")]

table=[-1 for i in range(K+1)]
table[1]=1


print(calc(N,K))

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

a = 10**9+7
count = [0 for i in range(k)]
sum = 0

res = n
e = []
while res != 0:
    e.append(res%2)
    res = res // 2

def exp(m, e, a):
    sum = 0
    ans = 1
    t = m
    for i in e:
        ans = (ans*(t**i))%a
        t = (t**2)%a
    return ans

for i in range(k, 0, -1):
    count[i-1] = exp(k//i, e, a)
    j = 2
    while i*j <= k:
        count[i-1] -= count[i*j-1]
        j += 1
    count[i-1] %= a
    sum += (i*count[i-1])%a

sum %= a
print(sum)

Solution (Python):
def main():
    mod=10**9+7
    def square(x,y):
        ret=1
        xx=x
        while y:
            if y%2==1:
                ret=ret*xx%mod
            xx=xx**2%mod
            y//=2
        return ret
    n,k=map(int,input().split())
    ans=0
    dp=[0]*(k+1)
    for i in range(k,0,-1):
        x=square(k//i,n)
        for j in range(2,k//i+1):
            x=(x-dp[i*j])%mod
        dp[i]=x
        ans=(ans+x*i)%mod  
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():
    n, k = LI()
    dp = [0] * (k + 1)
    for i in range(k, 0, -1):
        if i < 3:
            dp[i] += pow(k // i, n, mod)
            dp[i] %= mod
            if i != 1:
                dp[1] -= dp[i]
                dp[1] %= mod
        else:
            dp[i] += pow(k // i, n, mod)
            dp[i] %= mod
            j = 2
            while j ** 2 <= i:
                if i % j == 0:
                    dp[j] -= dp[i]
                    dp[j] %= mod
                    m = i // j
                    if m != j:
                        dp[m] -= dp[i]
                        dp[m] %= mod
                j += 1
            dp[1] -= dp[i]
            dp[1] %= mod
    ans = 0
    for i in range(k + 1):
        ans += i * dp[i]
        ans %= mod
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):


mod=1000000007
def p(a,b):
    if b==0:
        return 1
    z=p(a,b//2)
    z%=mod
    if b%2==1:
        return (a*z*z)%mod
    else:
        return (z*z)%mod
n,k=map(int,input().split())
dp=[0]*(k+3)


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

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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



def divisor(n):
    ans = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            ans.append(i)
            if i**2 == n:
                continue
            ans.append(n // i)
    return ans  


MOD = 10 ** 9 + 7

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

    c -= CNT[i]

    num += c

    f = divisor(i)
    for n in f:
        CNT[n] += c

    ans += c * i
    ans %= MOD


al = pow(K, N, MOD)
ans += al - num
ans %= MOD

print(ans)

Solution (Python):
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
def power_func(a,n,p):
  bi=str(format(n,"b"))
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res
N,K = map(int,input().split())
ans = K ** N
divdic = {1:1} 
for i in range(2,K+1):
    A = make_divisors(i)
    A.remove(i)
    X = i
    for j in A:
        X -= divdic[j]
    divdic[i] = X
    Y = K // i
    Z = X * (power_func(Y,N,mod)) % mod
    
    ans = (ans + Z) % mod
print(ans)

Solution (Python):
import bisect
import collections
import functools
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]



@functools.lru_cache(maxsize=None)
def f(x):
    return K//x
    a = 0
    for i in range(1, K + 1):
        if i % x == 0:
            a += 1
    return a % ACMOD


@functools.lru_cache(maxsize=None)
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 frozenset(divisors)


@functools.lru_cache(maxsize=None)
def get_diff(x):
    """
    xで割れるときにいくら増加するか
    2 -> 1 でカウント済みなので1
    """
    if x == 1:
        return 1
    ans = x
    for v in make_divisors(x):
        if v != x:
            ans -= get_diff(v)
    return ans % ACMOD


@functools.lru_cache(maxsize=None)
def pow(base_val, pow_val):
    if pow_val == 1:
        return base_val
    if pow_val == 0:
        return 1
    t = pow(base_val, pow_val // 2) % ACMOD
    return (t * t % ACMOD * (base_val if pow_val % 2 else 1)) % ACMOD






N, K = lmi()

ans = 0
for i in range(1, K + 1):
    ans += (pow(f(i), N) % ACMOD) * get_diff(i) % ACMOD
    

print(ans % ACMOD)

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

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)

  divisors.sort()
  return divisors
  
def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

div_table=[0,1]
for i in range(2,K+1):
  divlist=make_divisors(i)
  dv=i
  for d in divlist:
    if d<i:
      dv-=div_table[d]
  div_table.append(dv)

    
answer=0
for i in range(1,K+1):
  k=div_table[i]
  pm=powmod(K//i,N)
  answer+=k*pm
  answer%=MOD
  
print(answer)

Solution (Python):
M = 1000000007

N, K = [int(s) for s in input().split()]

A = [0] + [0 for _ in range(1, K+1)]
for k in range(K, 0, -1):
    if k * 2 > K:
        A[k] = 1
    else:
        A[k] = pow(K // k, N, M)
        i = 2
        while k * i <= K:
            A[k] -= A[k * i]
            i += 1

S = 0
for k in range(1, K+1):
    S = (S + A[k] * k) % M

print(S)

Solution (Python):
mod = 10**9+7
N,K = map(int,input().split())
p = [1]*(10**5+1)
for i in range(1,10**5+1):
    p[i] = pow(i,N,mod)
memo = [-1]*(K+1)
memo[1] = 1
def f(k):
    if memo[k] != -1:
        return memo[k]
    res = p[k]
    for n in range(2,k+1):
        res -= f(k//n)
    res %= mod
    memo[k] = res
    return res
ans = 0
for n in range(1,K+1):
    ans += n*f(K//n)
    ans %= mod

print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    cont = [0] * (K + 1)
    for i in range(K, 0, -1):
        tmp = K // i
        if tmp == 1:
            cont[i] = 1
        else:
            cont[i] = pow(tmp, N, MOD)
            for k in range(2,100000):
                if i * k > K:
                    break
                cont[i] -= cont[i*k]
                cont[i] %= MOD

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

    if sum(cont) % MOD != pow(K,N,MOD):
        ans -= sum(cont) % MOD - pow(K,N,MOD)

    print(ans)


if __name__ == "__main__":
    main()

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):
MOD = 10**9+7
N, K = map(int, input().split())
count = 0
ans = pow(K, N, MOD)
dictionary = [0 for _ in range(K+1)]
for i in range(K-1):
    j = K-i
    tmp = K // j
    tmp2 = pow(tmp, N, MOD)
    tmp2 -= sum(dictionary[::j])
    dictionary[j] = tmp2
    ans = (ans + (j-1) * tmp2)%MOD
    

print(ans)

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

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

div = [set() for _ in range(K+1)]
for i in range(2, K+1):
    for j in range(2*i, K+1, i):
        div[j].add(i)

pattern = [0]*(K+1)
for x in range(2, K+1)[::-1]:
    pattern[x] = (pattern[x] + pow(K//x, N, MOD)) % MOD
    for d in div[x]:
        pattern[d] = (pattern[d] - pattern[x] % MOD) % MOD
    pattern[1] = (pattern[1] - pattern[x]) % MOD
    
    ans = (ans + (pattern[x] * x) % MOD) %MOD

ans = (ans + (pow(K, N, MOD) + pattern[1]) % MOD ) % MOD

print(ans)

Solution (Python):
mod=1000000007
def powmod(a, n):
    global mod
    res = 1
    tmp=a
    while n>0:
        if n & 1 == 1:
            res = (res * tmp) % mod
        n=n//2
        tmp = tmp * tmp % mod
    return res
n,k=map(int, input().split())
appear_num = [0] * k
ans = 0
for gcm in range(k,0,-1):
    multi_num = k // gcm
    appear_num[gcm-1] = powmod(multi_num, n)
    for i in range(2, multi_num+1):
        appear_num[gcm-1] += mod - appear_num[i*gcm-1]
        appear_num[gcm-1] %= mod
    ans += gcm*appear_num[gcm-1]
    ans %= mod
print(ans)

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

def linput():
    return [int(x) for x in input().split()]

mod = 10**9 + 7

n, k = linput()

cnt = [0] * (k + 1)

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

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

ans = 0

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)

    divisors.sort()
    return divisors


for i in range(k, 0, -1):
    ans += cnt[i] * i
    ans %= mod
    d = make_divisors(i)
    for j in d:
        cnt[j] -= cnt[i]

print(ans)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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)
    divisors.sort()
    return divisors


MOD = 10 ** 9 + 7
N, K = lr()
answer = 0
reset = [0] * (K+1)
for i in range(1, K+1):
    num = K // i
    cmb = pow(num, N, MOD)
    arr = make_divisors(i)
    x = i
    for a in arr[:-1]:
        x -= reset[a]
    reset[i] = x
    answer += x * cmb

print(answer % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)

MOD = 10**9 + 7


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


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

d = {}


def func1(kk):
    
    if kk == 1:
        return 1
    if kk in d:
        return d[kk]

    cnt = 0
    for x in range(2, kk + 1):
        y = kk // x
        cnt += func1(y)

    d[kk] = (MOD + pow(kk, n, MOD) - cnt) % MOD
    return d[kk]


ans2 = 0
cnt = 0
for x in range(2, k + 1):
    y = k // x
    if y > 1:
        cnt = func1(y)
        ans2 += cnt * x % MOD
        ans2 %= MOD
    else:
        ans2 += x
        ans2 %= MOD

ans1 = func1(k)
ans = ans1 + ans2
ans %= MOD

print(ans)

Solution (Python):

mod = 10**9 + 7

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

ans = pow(K, N, mod)
cnts = [0] * (K + 1)
for k in range(K, 0, -1):
    r = K // k
    if r == 1:
        cnt = 1
        ans += (k - 1) * 1
    else:
        cnt = pow(r, N, mod)
        for c in range(2, r + 1):
            cnt -= cnts[k * c]
        cnt %= mod
        ans += (k - 1) * cnt

    cnts[k] = cnt
    ans %= mod

print(ans)

Solution (Python):
import math
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n))+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    d = {}
    r = 0
    for i in range(K, 0, -1):
        l = make_divisors(i)
        x = K // i
        t = pow(x, N, mod)
        if i in d:
            t -= d[i]
        for j in l:
            if j not in d:
                d[j] = t
            else:
                d[j] += t
        r += t * i
        r %= mod
    return r % mod
print(main())

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

MOD = 10**9+7

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

c = [0]*(k+1)

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

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

print(res)

Solution (Python):

import math
import collections
def main():

    N, K = map(int, input().split())
    mod = pow(10, 9) + 7

    p = collections.defaultdict(int)

    def fast_pow(x, y, mod):
        if y == 0: return 1
        if y % 2 == 0: return pow(fast_pow(x, y//2, mod), 2) % mod
        if y % 2 == 1: return (x * pow(fast_pow(x, y//2, mod), 2)) % mod

    ans = 0
    for i in range(K, 0, -1):
        v = fast_pow(K//i, N, mod) % mod
        u = v - p[i]
        tmp = (u * i) % mod
        for j in range(1, int(math.sqrt(i))+1):
            if i % j == 0:
                p[j] += u
                p[j] %= mod
                if i//j != j:
                    p[i//j] += u
                    p[i//j] %= mod
        ans += tmp
        ans %= mod
        
    return ans

if __name__ == '__main__':
    print(main())

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

dp=[0]*k
mod=10**9+7

ans=0
for i in range(k,0,-1):
    toori=pow(k//i,n,mod)

    dp[i-1]+=toori

    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]%mod

    ans+=(dp[i-1]*i)%mod


print(ans%mod)

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

L=[0 for i in range(N+1)]
E=[1 for i in range(N+1)]
E[0]=0
E[1]=0
for i in range(2,N+1):
    if E[i]==1:
        for j in range(2,N+1):
            if i*j>=N+1:
                break
            E[i*j]=0

L[1]=N

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

l=[0 for i in range(N+1)]
mod=10**9+7
ans=0
for i in range(N):
    cnt=pow(L[N-i],K,mod)
    for j in range(2,N+1):
        if (N-i)*j>=N+1:
            break
        cnt-=l[(N-i)*j]
    l[N-i]=(cnt%mod)
    ans+=(cnt%mod)


ANS=0
for i in range(len(l)):
    ANS+=i*l[i]
    ANS%=mod
print(ANS)

Solution (Python):
import sys
import time
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math

import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


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

def tasikame(n):
    ans = 0
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n + 1):
                tmp = math.gcd(i, j)
                ans += math.gcd(tmp, k)

    return ans


def main():
    n, k = getlist()
    ans = 0
    kumi = [0 for i in range(k+1)]
    for ii in range(k):
        i = k - ii
        cand = k // i
        
        tmp = pow(cand, n, MOD)
        
        
        
        
        
        
        
        
        
        
            
        tmp -= kumi[i]
        child = make_divisors(i)
        for ch in child:
            kumi[ch] += tmp
        
        ans += (tmp * i) % MOD
        ans %= MOD
        kumi[i] = tmp
        
    print(ans)
    

if __name__ == '__main__':
    main()

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

s = sum(cnt)
ans = pow(k,n,mod) - s
for i in range(k+1):
    ans += i*cnt[i]
    ans %= mod
print(ans)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict

con = 10 ** 9 + 7

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



def main():
	N, K = getlist()
	ans = 0
	L = [0] * (K + 1)
	for i in range(K):
		x = K - i
		val = pow(int(K // x), N, con)
		for j in range(2, int(K // x) + 1):
			val -= L[x * j]
		L[x] = (val % con)

	for i in range(1, K + 1):
		ans += L[i] * i
		ans %= con

	print(ans)

if __name__ == '__main__':
	main()

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

mod = 1000000007
ans = 0
dp = [0]*(k+1)

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

    j = 2
    divisor = [1]
    while j*j <= i:
        if i%j == 0:
            divisor.append(j)
            if j != i//j:
                divisor.append(i//j)
        j += 1

    for d in divisor:
        dp[d] -= dp[i]
        dp[d] = (dp[d]+mod)%mod


ans %= mod
print(ans)

Solution (Python):
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0


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

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

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

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

Solution (Python):
import numpy as np
N,K = map(int,input().split())
res = np.zeros(K+1, dtype=np.int64)
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)
    divisors.sort()
    return np.array(divisors, dtype=np.int64)

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

Solution (Python):
N, K = map(int, input().split())
MOD = 10**9+7
dp = [0] * (K+5)
ans = 0
for k in range(K, 0, -1):
    dp[k] = pow(K//k, N, MOD)

    i = 2
    while k * i <= K:
        dp[k] -= dp[k*i]
        i += 1
    
    ans += k * dp[k]
    ans %= MOD

print(ans)