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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()

def divisors(n):
    S,T=[],[]
    for i in range(1,int(n**.5)+1):
        if(n%i==0):
            S.append(i)
            T.append(n//i)
    T.reverse()
    return S+T if(S[-1]!=T[0]) else S+T[1:]

def resolve():
    n, k = map(int,input().split())
    C = [0] * (k + 1)
    for i in range(1, k + 1):
        C[i] = pow((k // i), n, MOD)

    for i in range(k, 1, -1):
        for d in divisors(i):
            if i == d:
                continue
            C[d] -= C[i]

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

    print(res)
resolve()

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

mod = 10**9+7


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


ans = 0
for i, c in enumerate(count):
    ans += i*c % mod

print(ans % mod)

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

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

print(ans)

Solution (Python):
N,K = map(int, input().split())
dp = [0]*(K+1)
MOD = 10**9+7
ans = 0
for X in range(K,0,-1):
  m = pow(K//X,N,MOD)
  x = 2*X
  while x<=K:
    m -= dp[x]
    m %= MOD
    x += X
  ans += X*m
  ans %= MOD
  dp[X] = m
print(ans)

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

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

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

print(sum(i*cnt[i] for i in range(1, k+1)) % m)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9 + 7

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

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

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

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

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k = m()

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

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

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

for i in range(1,k+1):
    co += ( dp[i] * i  )% mod
    co %= mod
print(co)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

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

print(ans)

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

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

for i in range(k, 0, -1):
    tmp = pow(k // i, n, 10**9 + 7)
    for j in range(i, k+1, i):
        tmp -= ansl[j]
    ansl[i] = tmp % (10**9 + 7)

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

Solution (Python):
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)

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

main()

Solution (Python):

n,k=map(int,input().split())
"""
3 2
->9
3 200
->10813692
100000 100000
->742202979
"""
ans = 0
xl=[0]*(k+1)
MOD = int(1e+9 + 7)

for x in range(k,0,-1):
    xl[x] = pow(k // x,n, MOD) 

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

ans = 0
for i in range(k+1):
    ans += i * xl[i]

print(ans % MOD)

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

ans=0
MOD=10**9+7

cnt=[0]*(K+1)
for x in reversed(range(1,K+1)):
    cnt_tmp = pow(K//x,N,MOD)
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t] 

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

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

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

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

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

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

ans=0
MOD=10**9+7

cnt=[0]*(K+1)
for x in reversed(range(1,K+1)):
    t = K//x
    cnt_tmp = pow(t,N,MOD)
    t=1
    while (t+1)*x<=K:
        t+=1
        cnt_tmp -= cnt[x*t]
    g = x*cnt_tmp %MOD
    cnt[x]+=cnt_tmp
    ans +=g
    ans%=MOD
print(ans)

Solution (Python):
MOD = int(1e+9 + 7)
N, K = map(int, input().split())
 
A = [0] * (K + 1) 
for x in range(1, K + 1):
    A[x] = pow(K // x, N, MOD)
 
for x in range(K, 0, -1): 
    for i in range(2, K // x + 1):
        A[x] -= A[x * i]

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

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

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

print(sum((i * cnt[i] for i in range(1, k + 1))) % p)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: print('Yes' if b else 'No')
YESNO=lambda b: print('YES' if b else 'NO')

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

if __name__ == '__main__':
    main()

Solution (Python):
N, K = [int(x) for x in input().split()]
mod = 1000000007
l = [pow(K//x, N, mod) for x in range(1, K+1)]
l.insert(0, 0)
ans = 0
for i in range(K, 0, -1):
    t = i * 2
    while(t <= K):
        l[i] -= l[t]
        t += i
for i in range(K+1):
    ans = (ans + l[i] * i) % 1000000007
if ans < 0:
    ans = 1000000007 - ans
print(ans)

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

As = [0]*(K+1)
X = K
while X>0:
    
    As[X] = pow((K//X),N,M)
    m = 2
    while m*X<=K:
        As[X] -= As[m*X]
        m += 1
    X -= 1


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

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

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

mod = 10 ** 9 + 7

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

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

Solution (Python):
n,k = map(int, input().split())
mod = 10**9+7
cnt = [0]*(k+1)
for i in reversed(range(2, k+1)):
    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
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))



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

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

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

x = [0 for _ in range(k+1)]

for i in range(k, 0, -1):
    x[i] = pow(k//i, n, MOD)
    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):

import sys

MOD = 1000000007  




def solve(N: int, K: int):
    
    
    
    
    
    
    

    
    
    sm = 0
    dic = dict()
    for i in range(K, 0, -1):
        n = modpow(int(K / i), N)
        n2 = n
        j = 2
        while i * j <= K:
            n2 -= dic.get(i * j)
            n2 %= MOD
            j += 1
        dic[i] = n2
        sm += i * n2
        sm %= MOD

    print(sm)


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



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

if __name__ == '__main__':
    main()

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

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

Solution (Python):
class ModInt:
    def __init__(self, value, mod=10**9 + 7):
        self.mod = mod
        self.value = value % mod

    def __add__(self, other):
        return ModInt(self.value + int(other) % self.mod, self.mod)

    def __sub__(self, other):
        return ModInt(self.value - int(other) % self.mod, self.mod)

    def __mul__(self, other):
        return ModInt(self.value * int(other) % self.mod, self.mod)

    def __pow__(self, power):
        return ModInt(pow(self.value, int(power), self.mod), self.mod)

    def __int__(self):
        return self.value

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

def main():
    n, k = map(int, input().split())
    g = [0] * k
    a = ModInt(0)
    for i in range(k, 0, -1):
        c = ModInt(k // i)**n
        for j in range(i * 2, k + 1, i):
            c -= g[j - 1]
        g[i - 1] = c
        a += c * i
    print(a)

if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache


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

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)

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

ans = 0
count=[0]*k
mod = 10**9+7
for i in range(0,k):
  kk=k-i
  maxi=k//kk
  count1=pow(maxi,n,mod)
  count2=0
  for j in range(2,maxi+1):
    count2 = count2 + count[j*kk-1]
  count[kk-1]=(count1 - count2)%mod

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

print(ans)

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

count_list = [0 for _ in range(k)]
for num in reversed(range(1,k+1)):
    
    count = pow(k//num,n,1000000007)
    count_list[num-1] = count

for num in reversed(range(1,k+1)):
    if k//num >= 2:
        for i in range(2,k//num+1):
            count_list[num-1] -= count_list[num*i-1]

score = 0
for idx,val in enumerate(count_list):
    score += (idx+1)*val

print(score%1000000007)

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

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

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

Solution (Python):


from math import gcd

def main():
     n, k = map(int, input().split())
     N = pow(10, 9) + 7
     gcd_num = [0 for i in range(k+1)]
     ans = 0

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

     print(ans%N)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict


def divisors(num):
    array = []
    limit = int(num ** 0.5) + 1
    for i in range(1, limit):
        if num % i == 0:
            div1 = i
            div2 = num//i
            array.append(div1)
            if div1 != div2:
                array.append(div2)
    array.sort(reverse=True)
    return array


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

counts = [0] * (k+1)
counts[1] = pow(k, n, mod)

for t in range(k, 1, -1):
    multiple_t = k // t
    pattern = pow(multiple_t, n, mod)
    counts[t] += pattern
    divs = divisors(t)
    for div in divs:
        if div == t:
            continue
        counts[div] -= counts[t]
        counts[div] %= mod

ans = 0
for value, count in enumerate(counts):
    ans += value * count % mod
    ans %= mod

print(ans)

Solution (Python):
import sys
readline = sys.stdin.readline
N, K = map(int, readline().split())
MOD = 10**9+7
table = [0]*(K+1)

for g in range(K, 0, -1):
    res = pow(K//g, N, MOD)
    for j in range(2*g, K+1, g):
        res = (res - table[j])%MOD
    table[g] = res
ans = 0
for g in range(1, K+1):
    ans = (ans + g*table[g])%MOD
print(ans)

Solution (Python):
N,K=map(int,input().split())
MOD=10**9+7
ans=0
X=[0]*K
for k in range(1,K+1):
  k=K+1-k
  x=K//k
  if x>1:
    _=pow(x,N,MOD)
    for i in range(x-1):
      _-=X[k*(i+2)-1]
    X[k-1]=_
    ans+=k*_
  else:
    X[k-1]=pow(x,N,MOD)
    ans+=k*X[k-1]
print(ans%MOD)

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

mod = 10**9+7

all_num = pow(k,n,mod)



ans = 0

dp = [0]*(k+1)

for i in range(k):
    tmp = k-i
    
    
    kazu = 1
    kakeru = 2
    heru = 0
    
    if tmp == 1:
        ans += all_num
        ans %= mod
        break
    
    
    for i in range(k//tmp-1):
        
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
    """
    while tmp * kakeru <= k:
        heru += dp[tmp*kakeru]
        kazu += 1
        kakeru += 1
        
    """ 
    
    kazu = pow(kazu,n,mod)-heru
    
    ans += tmp*(kazu)
    all_num -= (kazu)
    
    dp[tmp] = kazu
    ans %= mod
    
    
print(ans)

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

MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
ans = 0
for x in reversed(range(1, K + 1)):
    cnt[x] += pow(K // x, N, MOD)
    for n in range(2, K + 1):
        if x * n > K:
            break
        cnt[x] -= cnt[x * n]
    cnt[x] %= MOD
    ans += x * cnt[x] % MOD

print(ans % MOD)

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,K = LMIIS()
    
    

    
    

    
    



    
    
    ans = 0
    P = {}
    for i in range(K,0,-1):
        t = 2
        p = pow((K//i),N,MOD)
        while i*t<=K:
            p -= P[t*i]
            t += 1
        P[i] = p
        ans += p*i
        ans %= MOD
    print(ans)





    
    
    
    
    
    
    
    
    
    
    



if __name__ == '__main__':
    main()

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

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, K = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    a = [0]
    for d in range(1, K + 1):
        a.append(pow(K // d, N, MOD))
    
    for i in range(K, 0, -1):
        j = 2 * i
        while j <= K:
            a[i] = (a[i] - a[j]) % MOD
            j += i
    
    ans = 0
    for i in range(1, K + 1):
        ans = (ans + i * a[i]) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def main():
    n, k = map(int, input().split())
    count = [0]*(k+1)
    inf = pow(10, 9)+7
    for i in range(k, 0, -1):
        key = make_divisors(i)
        t = pow(k//i, n, inf)
        count[i] += t
        for value in key:
            if value == i:
                continue
            count[value] -= count[i]
    ans = 0
    for i in range(1, k+1):
        ans += ((count[i]%inf)*i)%inf
        ans %= inf
    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 range(k, 0, -1):
    c = pow(k // i, n, mod)
    c -= sum(cnt[i * 2::i])
    c %= mod
    cnt[i] = c

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

cnt = [0] * (k + 1)

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

    cnt[i] = c

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())
ans = 0
cnt_seq = [0]*(K+1) 
MOD = 10**9 + 7
ans = 0
for i in range(K,0,-1):
    cnt_seq[i] = pow(K//i,N,MOD)
    for j in range(2*i,K+1,i):
        cnt_seq[i] -= cnt_seq[j]%MOD
    ans += i*cnt_seq[i]%MOD
print(ans%MOD)

Solution (Python):
MOD = 10**9 + 7
def rep_sqr(base, k):
    ans = 1
    while k > 0:
        if k & 1:
            ans = ans * base % MOD
        base = base * base % MOD
        k >>= 1
    return ans

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

ans = 0

gcd = [0 for i in range(k+1)]
for i in reversed(range(1, k+1)):
    d = k // i
    
    gcd[i] = rep_sqr(d, n)
    
    j = i * d
    while j > i:
        gcd[i] -= gcd[j]
        j -= i
    ans += gcd[i] * i
    ans %= MOD

print(ans)

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

Solution (Python):
import sys,math,copy,queue,itertools,bisect
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
MOD = 10**9 + 7

N,K = LI()
ans = 0
for i in range(1,K+1):
    yaku = []
    for j in range(1,int(math.sqrt(i))+1):
        if i % j == 0:
            yaku.append(j)
            k = i // j
            if k != j:
                yaku.append(k)
    yaku.sort(reverse=True)
    num = []
    for y in yaku:
        ny = pow(K // y,N-1,MOD)
        for z in range(len(num)):
            if yaku[z] % y == 0:
                ny -= num[z]
        num.append(ny)
    for x,y in zip(num,yaku):
        ans = (ans + x * y) % MOD

print (ans)

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

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

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

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

def div(N):
  divv = []
  for i in range(1,int(N ** 0.5) + 1):
    if N % i == 0:
      divv.append(i)
      if i != N // i:
        divv.append(N // i)
  return(divv)
  
N,K = map(int,input().rstrip().split())
O = []
p = [0 for i in range(K + 1)]
ans = 0
for i in range(K,0,-1):
  p[i] = modpow(int(K / i),N,1000000007)
for i in range(K,0,-1):
  ans = (ans + (p[i] * i)) % 1000000007
  O = div(i)
  for o in O:
    if o != i:
      p[o] -= p[i]
print(ans)

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

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

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

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

Solution (Python):
N, K = map(int, input().split())
p = 10**9+7
S = 0
memo = []
for i in reversed(range(1, K+1)):
  rep = K//i
  num = pow(rep, N, p)
  sub = 0
  if rep > 1:
    for j in range(rep - 1):
      sub += memo[- i - j * i][1]
  num -= sub
  S += i * num
  S = S%p
  memo += [(i, num)]
print(S)

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

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

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

print(ans%MOD)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
data = [0] * (k+1)
for i in range(k,0,-1):
  tmp = pow(k//i,n,mod)
  for j in range(i+i,k+1,i):
    tmp -= data[j]
  data[i] = tmp % mod
ans = 0
for i,di in enumerate(data):
  ans += i * di
  ans %= mod
print(ans)

Solution (Python):

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














ans=0 
GCD=[0 for _ in range(K+1)] 
for x in range(K,0,-1): 
    Ai_cnt=K//x 
    rep=0 

    
    check=2*x
    while check<=K: 
        rep+=GCD[check] 
        check+=x 

    
    GCD[x]=pow(Ai_cnt,N,MOD)-rep 
    
    ans+=x*(GCD[x])
    ans%=MOD








print(ans)

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

ans=0
i=K
while i>=1:
    H[i]=pow(K//i,N,m)
    j=2
    while j*i<=K:
        H[i]-=H[j*i]
        j+=1
    ans+=H[i]*i
    i-=1


print(ans%m)

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

def phi_table(N):
    phi = list(range(N + 1))
    for p in range(2, N + 1):
        if phi[p] == p:
            for n in range(N // p, 0, -1):
                phi[p * n] -= phi[n]
    return phi


L = int(N ** .66)
H = int(N // (L + 1))
phi = phi_table(L)



f_l = phi.copy()
for n in range(L):
    f_l[n + 1] += f_l[n]

f_h = [0] * (H + 1)  


def f(n):
    return f_l[n] if n <= L else f_h[N // n]


def compute_f(n):
    sq = int(n ** .5)
    x = n * (n + 1) // 2
    for d in range(1, n + 1):
        m = n // d
        if m <= sq:
            break
        x -= f(m)
    for m in range(1, sq + 1):
        cnt = n // m - n // (m + 1)
        x -= f_l[m] * cnt
    return x


for d in range(H, 0, -1):
    f_h[d] = compute_f(N // d)

sq = int(N ** .5)
answer = 0
for d in range(1, N + 1):
    n = N // d
    if n <= sq:
        break
    answer += pow(n, e, MOD) * phi[d]

for n in range(1, sq + 1):
    low_d = N // (n + 1)
    high_d = N // n
    phi_sum = f(high_d) - f(low_d)
    answer += phi_sum * pow(n, e, MOD)

answer %= MOD
print(answer)

Solution (Python):

MOD = 10**9 + 7

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

c = 0

d = [0] * (k + 1)

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

        
    if d[i] == 0:

        
        t1 = k // i    
        c1 = pow(t1, n, MOD)

        j = i
        while j + i <= k:
            j += i
            c1 -= d[j]
            if c1 < 0:
                c1 += MOD

        d[i] = c1

        

        c += i * c1
        c %= MOD

print (c)

Solution (Python):

MOD = 10**9 + 7

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

c = 0

d = [0] * (k + 1)

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

        
    if d[i] == 0:

        
        t1 = k // i    
        c1 = pow(t1, n, MOD)

        j = i
        while j + i <= k:
            j += i
            c1 -= d[j]
            if c1 < 0:
                c1 += MOD

        d[i] = c1

        

        c += i * c1
        c %= MOD

print (c)

Solution (Python):
import math
import fractions
import collections
import itertools





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

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

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

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