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 = [int(i) for i in input().split(' ')]
MOD = 10 ** 9 + 7

COUNT = {}
for i in range(K,0,-1):
    whole = pow((K//i), N, MOD)

    c = 2
    while i * c <= K:
        whole -= COUNT[i*c]
        c += 1

    COUNT[i] = whole % MOD

SUM = 0
for k, v in COUNT.items():
    SUM += k * v
    SUM %= MOD

print(SUM)

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):
N,K=map(int,input().split())
ans=0
mod=10**9+7
A=[0 for i in range(K)]
for i in range(K,0,-1):
  l=pow(K//i,N,mod)
  a=2
  while a*i<=K:
    l-=A[a*i-1]
    a+=1
  ans+=l*i%mod
  ans%=mod
  A[i-1]=l
print(ans)

Solution (Python):


n, k = map(int, input().split())
X = [0]*(k+1)
mod = 10**9+7

for x in range(k, 0, -1):
    
    X[x] = pow(k//x, n, mod)
    for x_multi in range(x*2, k+1, x):
        X[x] -= X[x_multi]

print(sum((i*x)for i, x in enumerate(X))%mod)

Solution (Python):
def ff(n):
    i = 1
    r = set()
    while i * i <= n:
        if n % i == 0:
            r.add(i)
            if i != n // i:
                r.add(n // i)
        i += 1
    return sorted(r)

def main():
    N, K = map(int, input().split())
    mod = 10**9 + 7
    T = [[] for _ in range(K + 1)]
    F = [ff(i) for i in range(K + 1)]
    for i, f in enumerate(F[1:], 1):
        for j in f:
            T[j].append(i)
    r = 0
    t = [0] * (K + 1)

    for i in reversed(range(1, K + 1)):
        q = (pow(len(T[i]), N, mod) - t[i]) % mod
        for j in F[i][:-1]:
            t[j] = (t[j] + q) % mod
        r = (r + i * q) % mod

    return r

print(main())

Solution (Python):
n,k = map(int,input().split())
x = [0]*k
mod = 10**9+7
def power(a,n):
  ans = 1
  while n:
    if n%2:
      ans = (ans*a)%mod
    a = (a*a)%mod
    n >>= 1
  return ans%mod  
for i in range(k,0,-1):
  c = power(k//i,n)
  j = 2
  while i*j <= k:
    c -= x[i*j-1]
    j += 1
  x[i-1] = c
s = 0
for i in range(1,k+1):
  s = (s + i*x[i-1])%mod
print(s)

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

Solution (Python):
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)


def get_nums_l():
    return [ int(s) for s in input().split(" ")]


def get_nums_n(n):
    return [ int(input()) for _ in range(n)]


def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

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


n,k = get_nums_l()
MOD = 10**9+7

ans = 0
count = [0] * (k+1)
for x in range(k, 0, -1):
    count[x] = pow((k//x),n,MOD)

    for y in range(x*2, k+1, x):
        count[x] -= count[y]

print(sum([ x*i for i,x in enumerate(count) ]) % MOD)

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

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

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

ans = sum([num * c for num, c in enumerate(cnt)]) % MOD
print(ans)

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

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

ans += pow(K, N, MOD)-sum(cnt[2:])
ans %= MOD

print(ans)

Solution (Python):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K = MAP()

mod = 10**9+7

cnt = [0]*K


for i in reversed(range(1, K+1)):
    a = pow(K//i, N, mod)
    cnt[i-1] = a

    b = 2
    while b*i <= K:
        cnt[i-1] -= cnt[b*i-1]
        b += 1

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

print(ans % mod)

Solution (Python):
N, K = map(int, input().split())
li = [0]*(K+1)

out = 0
mod = 10**9+7

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

Solution (Python):
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
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 x in range(1, K + 1):
  ans += cnt[x] * x
print(ans % MOD)

Solution (Python):
N, K = map(int, input().split())
li = [0]*(K+1)

out = 0
mod = 10**9+7

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

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

MOD = 10**9 + 7
A = [0] * (K + 1)


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


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

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

Solution (Python):
import math
N,K= map(int, input().split())
a=[0]*(K+1)
co=0
mod=(10**9+7)
for i in range(K,0,-1):

    b=K//i
    t=2*i
    m=0
    while t<=K:
        m=m+a[t]
        t+=i
    c=pow(b,N,mod)
    a[i]=c-m
    co+=(a[i]*i)%mod


print(co%mod)

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

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

print (ans)

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

mod = 10**9+7
cnts=[0]*(k+1)

for x in reversed(range(1,k+1)):
    num= k//x

    c = pow(num,n,mod)
    for j in range(2,num+1):
        c-= cnts[x*j]
    cnts[x]=c

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

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

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

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

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

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


dp = [0] * (K + 1)
for k in reversed(range(1, K + 1)):
    cnt = pow(K // k, N, MOD)
    for i in range(2, K + 1):
        if i * k > K:
            break
        cnt -= dp[i * k]
    dp[k] = cnt

ans = 0
for k, cnt in enumerate(dp):
    ans += k * cnt
    ans %= MOD
print(ans % MOD)

Solution (Python):
from collections import Counter


def read():
    N, K = list(map(int, input().strip().split()))
    return N, K


def n_gcd(k, N, K, cache, MOD=10**9+7):
    if cache[k] != -1:
        return cache[k]
    n = pow(K // k, N, MOD)
    for j in range(2*k, K+1, k):
        n -= n_gcd(j, N, K, cache)
        n %= MOD
    cache[k] = n
    return n


def solve(N, K, MOD=10**9+7):
    cache = [-1 for k in range(K+1)]
    ans = 0
    for k in range(K, 0, -1):
        ans += n_gcd(k, N, K, cache) * k
        ans %= MOD
    return ans

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

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


def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = ans*x
      ans %= mod
    x = x*x
    x %= mod
    n = n >> 1
  return ans % mod

nums = [0 for _ in range(10**5 + 1)]

def f(i, N, K):
    
    
    cnt = pow(K // i, N)
    
    j = i
    while j + i <= K:
        cnt -= nums[j+i]
        j += i
    nums[i] = cnt
    return nums[i]

def main():
    N, K = LI()
    cnt = 0
    for i in range(1, K+1)[::-1]:
        cnt += (i * f(i, N, K) % mod)
        cnt %= mod
    print(cnt)

main()

Solution (Python):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
mod = 10**9+7
N, K = map(int, input().split())
ans = 0
cnt = np.zeros(K+1, np.int64)
for X in reversed(range(1,K+1)):
	a = K // X
	cnt[X] = pow(a,N,mod)
	x = 2
	res = 0
	while True:
		tmp = X * x
		if tmp > K:
			break
		res += cnt[tmp]
		res %= mod
		x += 1

	cnt[X] -= res
	cnt[X] %= mod
	ans += cnt[X] * X
	ans %= mod

print(ans)

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

def power(a,x): 
    T=[a]
    while 2**(len(T))<mod: 
        T.append(T[-1]**2%mod)
    b=bin(x) 
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans

for i in range(k):
    cnt=power(k//(k-i),n)
    now=(k-i)*2
    while now<=k:
        cnt-=A[now-1]
        now+=k-i
    A[k-i-1]=cnt

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

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

print(answer)

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

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

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


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


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

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

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

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

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

Solution (Python):
a= list(map(int,input().split()))
N = a[0]
K = a[1]

a = [0]*K
mod = 10**9+7

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

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

ans = s%mod

print(ans)

Solution (Python):

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

MOD = 10**9+7


gcd_dict = {}
for i in range(K, 0, -1):

    number = pow((K//i), N, MOD)
    number %= MOD
    counter = 2
    while True:
        if counter*i in gcd_dict:
            number -= gcd_dict[counter*i]
            counter += 1
        else:
            gcd_dict[i] = number % MOD
            break

print(sum([i*j for i, j in gcd_dict.items()]) % MOD)

Solution (Python):
import copy

MOD = 10 ** 9 + 7

def pow_k(x, n, mod):
  if n == 0:
    return 1

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

    n //= 2

  return (x * K) % mod

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

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

Solution (Python):
import copy

MOD = 10 ** 9 + 7

def pow_k(x, n, mod):
  if n == 0:
    return 1

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

    n //= 2

  return (x * K) % mod

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

array = [0] * (k+1)
for i in range(1, k+1):
  tmp = k // i
  array[i] = pow_k(tmp, n, MOD)
  
ans = 0
for i in reversed(range(1,k+1)):
  for j in range(i*2,k+1,i):
    array[i] -= array[j]
    
  ans += array[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):
def solve():
    N, K = map(int,input().split())
    mod = 10 ** 9 + 7

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

if __name__ == '__main__':
    solve()

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

cnt = [0] * (K + 1)

def calc(x):
    M = K // x
    c = pow(M, N, MOD)
    for i in range(x + x, K + 1, x):
        c -= cnt[i]
    cnt[x] = c
    return c * x

ans = 0
for x in range(1, K + 1)[::-1]:
    ans = (ans + calc(x)) % MOD
print(ans)

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

L=[0]*(K+1)
for i in range(1,K+1)[::-1]:
    minus=0
    count=2
    while True:
        if count*i<=K:
            minus+=L[count*i]
            minus=minus%P
            count+=1
        else:
            break

    L[i]=(pow(K//i,N,P)-minus)%P

ans=0
for j in range(1,K+1):
    ans+=j*L[j]
    ans=ans%P

print(ans)

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

patterns = [0] * k
total = 0

for i in range(k, 0, -1):
    
    
    tmp = pow(k // i, n, MOD)

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

print(total)

Solution (Python):
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)


inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import Counter
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))



def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  


def grid(n): return [s_list() for _ in range(n)]


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


def main():
    N, K = wi()
    mod = 10 ** 9 + 7
    res = 0
    d = [0]*K

    for i in range(K, 0, -1):
        n = pow(K//i, N, mod)

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

        d[i-1] = n
        res += n*i
        res %= mod
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
mod = 1000000007

def pow_mod(x, y):
    res = 1
    while y > 0:
        if y % 2:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y //= 2
    return res

def divs(x):
    res = []
    for i in range(1, x+1):
        if i * i > x:
            break
        if x % i != 0:
            continue
        res.append(i)
        if i != x // i:
            res.append(x // i)
    return res

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

num = [0] * 100010
for g in range(1, K+1):
    num[g] = pow_mod(K // g, N)


for x in range(K, 0, -1):
    div = divs(x)
    for i in div:
        if i == x:
            continue
        num[i] += mod - num[x]
        num[i] %= mod

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

Solution (Python):
def main():
    N, K = map(int, input().split())
    MOD = 10**9 + 7
    cnt = [0 for _ in range(K)] 
    ans = 0

    for k in range(K)[::-1]:
        x = k+1

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

        ans += cnt[k]*x
        ans %= MOD
    print(ans)
main()

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
count = Counter()
for i in reversed(range(1, K + 1)):
    c = pow(K // i, N, MOD)
    j = 2
    while i * j <= K:
        c -= count[i * j]
        j += 1
    count[i] = c
print(sum(i * j for i, j in count.items()) % MOD)

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *
 
sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = map(int, input().split())
count = Counter()
for i in reversed(range(1, K + 1)):
    c = pow(K // i, N, MOD)
    j = 2
    while i * j <= K:
        c -= count[i * j]
        j += 1
    count[i] = c
print(sum(i * j for i, j in count.items()) % MOD)

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

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

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

Solution (Python):
N, K = map(int, input().split())
p = int(1e9+7)
res = 0
d = [0]*K

for i in range(K, 0, -1):
    n = pow(K//i, N, p)

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

    d[i-1] = n
    res += n*i
    res %= p

print(res)

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from bisect import bisect_left,bisect_right
from collections import deque

    
def main():
    n,k = map(int,input().split())
    ans = 0
    G = [0] * (1 + k)
    for g in range(k,0,-1):
        ret = pow((k//g),n,MOD)
        for j in range(2 * g,k + 1,g):
            ret -= G[j]
        G[g] = ret
        ans += ret * g
        ans %= MOD
    
    print(ans) 

if __name__ =='__main__':
    main()

Solution (Python):
import numpy as np
n,k = map(int,input().split())
m = 10**9 + 7
gcds = np.zeros(k+1, int)
ans = 0

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

Solution (Python):
from collections import defaultdict

N, K = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)

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

Solution (Python):
import numpy as np
n,k = map(int,input().split())
m = 10**9 + 7
gcds = np.zeros(k+1, int)

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

Solution (Python):
import math

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

dic = {} 
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i 
    if t > k/2: 
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Solution (Python):
import math

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

dic = {} 
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i 
    if t > k/2: 
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

Solution (Python):
MOD = 1000000007
def mod_pow(x , y):
    if y == 0:
        return 1
    if y == 1:
        return x
    r = mod_pow(x , y // 2)
    r2 = (r * r) % MOD
    if y % 2 == 0:
        return r2 % MOD
    else:
        return (r2 * x) % MOD

N , K = map(int , input().split())
result = 0
memo = {}
for g in range(K , 0 , -1):
    comb = mod_pow(K // g , N)
    for j in range(2 , K // g + 1):
        comb = (comb - memo[j * g] + MOD) % MOD
    memo[g] = comb
    result = (result + comb * g) % MOD
print(result)

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

mod=10**9+7

pow_table={}
def eco_pow(x):
    if x in pow_table:
        return pow_table[x]
    else:
        pow_table[x]=pow(x,n,mod)
        return pow_table[x]
    
ans=0
res_dic={}
for i in range(k):
    now=k-i
    all_now_res=eco_pow(k//now)
    del_now_res=0

    for q in range(2*now,k+1,now):
        
        del_now_res+=res_dic[q]

    res_dic[now]=(all_now_res-del_now_res)%mod
    
    ans+=res_dic[now]*now
    ans%=mod

print(ans)

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

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

for x in range(K,0,-1):
  num[x]=pow(K//x,N,DIV)
  for temp in range(x*2,K+1,x):
    num[x]-=num[temp]
  ans += num[x] * x
  ans %= DIV

print(ans)

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

cnt = dict(zip(range(1,k+1), [0] * k))
for i in range(1, k+1)[::-1]:
    cnt[i] = pow((k // i), n, 10**9+7)

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

print(ans % (10 ** 9 + 7))

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

ns = [0] * n
ans = 0

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

for i in range(n,0,-1):
    
    ns[i-1] = modpow(n//i,k)
    for j in range(2*i,n+1,i):
        ns[i-1] -= ns[j-1]
    ans += (i * ns[i-1])%(10**9+7)
    ans %= (10**9+7)

print(ans)

Solution (Python):
import math

def pow(p,n):
    bin_n=bin(n)[2:][::-1]
    tmp=p;pn=1
    for i in range(len(bin_n)):
        if bin_n[i]=="1": pn=(pn*tmp)%mod
        tmp=tmp*tmp%mod
    return pn


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

ans=[0]*(k+1)
for i in range(k,0,-1):
    div=set()
    for x in range(1,int(i**0.5)+1):
        if i%x==0: div.add(x);div.add(i//x)
    ans[i]=pow(k//i,n)-sum([ans[j*i] for j in range(k//i,1,-1)])
    ans[i]%=mod
print(sum(ans[i]*i for i in range(k+1))%mod)

Solution (Python):
import math

def pow(p,n):
    bin_n=bin(n)[2:][::-1]
    tmp=p;pn=1
    for i in range(len(bin_n)):
        if bin_n[i]=="1": pn=(pn*tmp)%mod
        tmp=tmp*tmp%mod
    return pn


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

ans=[0]*(k+1)
for i in range(k,0,-1):
    div=set()
    for x in range(1,int(i**0.5)+1):
        if i%x==0: div.add(x);div.add(i//x)
    ans[i]=pow(k//i,n)-sum([ans[j*i] for j in range(k//i,1,-1)])
    ans[i]%=mod

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

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

ans = 0
for i in range(k):
    ans += (i+1) * l[i]
print(ans % (10**9+7))

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

ans = 0
for i in range(k):
    ans += (i+1) * l[i]
print(ans % (10**9+7))

Solution (Python):
N,K=map(int,input().split())
mod=10**9+7
GCD=[0 for _ in range(K+1)]
for i in range(1,K+1):
    GCD[i]=pow(K//i,N,mod)

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

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

gcd = [0] * k
for i in range(k):
    test = k - i
    temp = 0
    for j in range(k // test):
        if j == 0:
            temp2 = 1
            temp3 = [k // test]
            for l in range(len(bin(n)) - 2):
                temp3.append(temp3[-1] ** 2 % mod)
            test3 = bin(n)
            for l in range(len(test3) - 2):
                if test3[-1-l] == "1":
                    temp2 *= temp3[l]
                    temp2 %= mod
            temp += temp2
        else:
            test2 = test * (j + 1)
            temp -= gcd[test2 - 1]
    gcd[test - 1] = temp
ans = 0
for i in range(k):
    ans += gcd[i] * (i + 1)
    ans %= mod
print(ans)

Solution (Python):
from math import sqrt

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

fn=[0 for i in range(0,K+1)]
fn[0]=0
fn[1]=1
for i in range(2,K+1):
    I=int(sqrt(i))
    s=sum(fn[i//g] for g in range(1,I+1))
    t=0
    r=i//(I+1)
    for j in range(1,r+1):
        t=(t+(i//j-i//(j+1))*fn[j])%mod
    fn[i]=(pow(i,N,mod)-s-t)%mod

ans=0
for g in range(1,K+1):
    ans=(ans+g*fn[K//g])%mod

print(ans)

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

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

Solution (Python):
def pow(b, e):
    res = 1
    while e:
        if e & 1:
            res = (res * b) % MOD
        e >>= 1
        b = (b * b) % MOD
    return res


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

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


num_sequence_list = [0] * (MaxNum + 1)

total_value = 0
for i_divisor in range(MaxNum, 0, -1):
    num_sequence = pow(MaxNum//i_divisor, NumSeq, mod)

    for j_multiple in range(2, MaxNum//i_divisor+1):
        num_sequence -= num_sequence_list[i_divisor*j_multiple]

    num_sequence_list[i_divisor] = num_sequence
    total_value += num_sequence * i_divisor

print(total_value % mod)

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

num_gcd_k = [0]*(k+1)
num_gcd_k[k] = 1
ans = 0
for i in range(k,0,-1):
    
    total = pow(k//i,n,mod)
    m = 2
    while i*m <= k:
        total -= num_gcd_k[i*m]
        m += 1
    num_gcd_k[i] = total
    ans += i*total
    ans %= mod

print(ans)

Solution (Python):



import sys
input = sys.stdin.readline
N, K = map(int, input().split())
md = pow(10,9) + 7

cnt_memo = [0]*(K+1)
cnt_R_memo = [0]*(K+1)

def main():
    ret = 0
    for k in range(1,K+1):
        cnt_R_memo[k]=pow(K//k,N,md)
    for k in range(K,0,-1):
        cnt_memo[k]=(cnt_R_memo[k] - sum(cnt_memo[2*k::k]))%md
        ret += (cnt_memo[k]*k)%md
    print(ret%md)

if __name__ == '__main__':
    main()

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

    ans += i*a2
    l[i] = a2
    ans %= mod
    
print(ans)

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import sqrt

def prime_division(x):
    q = int(sqrt(x))
    a = []
    for i in range(2,q+1):
        ex = 0
        while x%i == 0:
            ex += 1
            x //= i
        if ex>0:
            a.append([i,ex])
    if x>q:
        a.append([x,1])
    return a

def divisorlist(z): 
    
    if len(z)==1:
        return [z[0][0]**i for i in range(z[0][1]+1)]
    y = divisorlist(z[1:])
    s = []
    for i in range(z[0][1]+1):
        for j in y:
            s.append((z[0][0]**i)*j)
    return s

n,k = inm()
d = [0]*(k+1)
d[1] = pow(k,n,R)
sm = 0
for i in range(k,1,-1):
    d[i] = (d[i]+pow(k//i,n,R))
    ps = divisorlist(prime_division(i))
    for p in ps:
        if p!=i:
            d[p] = (d[p]-d[i])%R
    sm = (sm+d[i]*i)%R

print((sm+d[1])%R)