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
import math



def input():
    return sys.stdin.readline().rstrip()


def main():
    mod = 10 ** 9 + 7

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

    C =[0] *(K+1)

    for k in range(K,1,-1):
        num = K//k
        count = pow(num,N,mod)
        while num>1:
            count -= C[num*k]
            count %=mod
            num-=1
        C[k] =count
    ans =0
    for i in range(K+1):
        ans += i*C[i]
        ans %=mod
    ans += pow(K,N,mod) -sum(C)

    print(ans%mod)



if __name__ == "__main__":
    main()

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


def solve(N, K):
    ans = 0
    numExact = [0] * (K + 1)
    for g in reversed(range(1, K + 1)):
        
        
        numGreaterEq = pow(K // g, N, MOD)
        
        numGreater = 0
        for multipleG in range(2 * g, K + 1, g):
            numGreater += numExact[multipleG]
        numExact[g] = numGreaterEq - numGreater
        ans += g * numExact[g]
        ans %= MOD

    return ans


if False:
    import random
    from itertools import product
    from math import gcd

    random.seed(0)
    for _ in range(10000):
        N = random.randint(1, 1)
        K = random.randint(1, 10)

        brute = 0
        for arr in product(range(1, K + 1), repeat=N):
            g = 0
            for x in arr:
                g = gcd(g, x)
            brute += g
        brute = brute % MOD

        ans = solve(N, K)
        
        assert ans == brute


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

print(solve(N, K))

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





N, K = MAP()

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

print(ans)

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





N, K = MAP()

gcd_cnt = [0]*(K+1)

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

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

print(ans)

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

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

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

l = [0]*(k+1)

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

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

Solution (Python):

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

d = [-1 for _ in range(k+1)]
d[k] = 1 

for i in range(k-1, 0, -1):
    d[i] = pow(k//i, n, mod)
    j = 2*i 
    while j <= k:
        d[i] -= d[j]
        j += i


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

Solution (Python):
N,K=map(int,input().split())
mod=10**9+7
X=[0]+[pow(K//d,N,mod) for d in range(1,K+1)]
'''
Y=[[] for i in range(K+1)]
for i in range(1,K+1):
    for j in range(i,K+1,i):
        Y[j].append(i)
'''

isPrime=[1 for i in range(K+1)]
isPrime[0]=0;isPrime[1]=0
for i in range(K+1):
    if isPrime[i]==0:
        continue
    for j in range(2*i,K+1,i):
        isPrime[j]=0
Mebius=[1 for i in range(K+1)]
Mebius[0]=0
for i in range(2,K+1):
    if isPrime[i]==0:
        continue
    for j in range(i,K+1,i):
        Mebius[j]*=-1
for i in range(2,K+1):
    for j in range(i*i,K+1,i*i):
        Mebius[j]=0
Z=[0 for i in range(K+1)]
for i in range(1,K+1):
    for j in range(i,K+1,i):
        Z[i]+=X[j]*Mebius[j//i]
ans=0
for i in range(1,K+1):
    ans+=Z[i]*i
    ans%=mod
print(ans)
'''
P(G%d==0)
Gがd,2d,3d,...の可能性がある
P(d)-P(2d)-P(3d)-P(5d)+P(6d)-P(7d)
'''

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

a = [0]*(k+1)

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

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

print(ans % mod)

Solution (Python):
import numpy as np
from numba import jit

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

@jit
def main():
  mod=10**9+7
  L=np.zeros(k+1,dtype='int64')
  ans=0
  for x in range(k,0,-1):
    lx=pow((k//x),n,mod)
    cnt=1
    while x*(cnt+1)<=k:
      cnt+=1
      lx-=L[x*cnt]
    L[x]=lx%mod
    ans+=(L[x]*x)%mod
  return ans%mod

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

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

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

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

mod = 10**9+7

def power(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

X = [0]*(k+1)

ans = 0
for g in reversed(range(1, k+1)):
    temp = power(k//g, n, mod)
    j = g
    while j <= k:
        temp -= X[j]
        j += g
    ans += temp*g
    X[g] = temp
ans %= mod
print(ans)

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

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

Solution (Python):
N, K = map(int, input().split())
MOD = 1_000_000_007
gcd_cnt = [0] * (K + 1)
for g in range(K, 0, -1):
    gcd_cnt[g] = pow(K // g, N, MOD)
    for g_mul in range(2, K // g + 1):
        gcd_cnt[g] -= gcd_cnt[g * g_mul]

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

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

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

cnt = [0] * (K + 1)

ans = 0
total = 0
for i in range(K, 0, -1):
    t = K // i
    now = my_pow(t, N, MOD)
    for j in range(i*2, K + 1, i):
        now -= cnt[j]
    cnt[i] = now
    ans += (now * i) % MOD
print(ans % MOD)

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))


INF=10**20
def main():
    N,K=mi()
    MOD = 10**9+7

    ans = 0
    dic = {} 
    for x in range(K,0,-1):  
        p_count = K//x
        count = pow(p_count,N,MOD)

        i = 2
        while x*i <= K:
            if not x*i in dic: break
            count -= dic[x*i]
            count %= MOD
            i += 1

        count %= MOD
        dic[x] = count
        
        ans += count * x
        ans %= MOD
        
    
    print(ans)








if __name__ == "__main__":
    main()

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

ans = 0
A = [0 for _ in range(K+1)]
for i in range(1,K+1):
  ans += pow(K//i, N, MOD) * (i - A[i])
  ans %= MOD
  
  
  j = 2*i
  while j <= K:
    A[j] += i - A[i]
    j += i
    
print(ans)

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


def main():
    N, K = (int(i) for i in input().split())
    g = [0]*(K+1)
    for k in range(1, K+1)[::-1]:
        cnt = K//k
        g[k] += pow(cnt, N, MOD)
        p = k
        while p + k <= K:
            p += k
            g[k] -= g[p]
        g[k] %= MOD
    ans = 0
    for i, g in enumerate(g[1:], start=1):
        ans += i*g
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

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

divisor_lst = [i - 1 for i in range(1, k + 1)]
divisor_lst[0] = 1

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

ans = 0
for num in range(1, k + 1):
    ans += pow(k // num, n, MOD) * divisor_lst[num - 1]
    ans %= MOD
print(ans)

Solution (Python):

 
N, K = map(int, input().split())
mod = 10**9 + 7
def main():
  b = N
  blis = []
  c = 0
  while b >0:
    if b & 1 == 1:
      blis.append(c)
    c += 1
    b >>= 1


  def modpow(a, blis= blis, c = c):
    if a == 1:
      return 1
    else:
      res = 1
      li = []
      for _ in range(c):
        li.append(a%mod)
        a = a*a%mod
      for item in blis:
        res = res *li[item] %mod
      return res

    
  fact_count = [0 for _ in range(K+1)]
  for k in range(1, K+1):
    fact_count[k] = K//k

  ans = 0
  count = [0 for _ in range(K+1)]
  for k in range(K, 0, -1):
    x = 1*fact_count[k]
    cc = modpow(x)
    j = 2*k
    l = 2
    while(j<=K):
      cc -= count[j]
      l += 1
      j = k*l
    count[k] = cc
    cc = cc*k%mod
    ans += cc
    ans %= mod
  print(ans)
if __name__ == '__main__':
  main()

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

  
fact_count = [0 for _ in range(K+1)]
for k in range(1, K+1):
  fact_count[k] = K//k

ans = 0
count = [0 for _ in range(K+1)]
for k in range(K, 0, -1):
  c = pow(fact_count[k], N, mod)
  j = 2*k
  l = 2
  while(j<=K):
    c -= count[j]
    l += 1
    j = k*l
  count[k] = c
  c = c*k%mod
  ans += c
  ans %= mod
print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N, K  = list(map(int, input().split()))
ans = [0 for i in range(K+1)]

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



b = [i*ans[i] % mod for i in range(K+1)]
print(sum(b) % mod)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

class Eratosthenes:
    
    def __init__(self, n):
        primes = []
        lp = [0] * (n + 1)

        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n:
                    break
                lp[i * pj] = pj
        self.primes = primes
        self.lp = lp

    def is_prime(self, x):
        return self.lp[x] == x

    def factrization(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N, K = LI()

    era = Eratosthenes(K)
    count = [0] * (K + 1)

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

    for i in range(1, K + 1)[::-1]:
        divs = era.factrization(i)
        candedates = [l for l in set(reduce(lambda x, y:x * y, ll, 1) for r in range(1, len(divs) + 1) for ll in itertools.combinations(divs, r))]
        for v in candedates:
            count[i // v] -= count[i]

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

if __name__ == '__main__':
    main()

Solution (Python):
def power(x, n, mod):
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans = ans * x % mod
        n //= 2
        x = x * x % mod
    return ans

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

mod = 10 ** 9 + 7

count = [0] * k
for i in range(k, 0, -1):
    count[i-1] = power(k // i, n, mod)
    j = i * 2
    while j <= k:
        count[i-1] -= count[j-1]
        j += i

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

Solution (Python):

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

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

for x in reversed(range(1, K + 1)):
    ctr[x] = pow(K // x, N, MOD)
    for y in range(2 * x, K + 1, x):
        ctr[x] -= ctr[y]

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

print(ans)

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


def a(n):
    if n in memo:
        return memo[n]
    else:
        ret = pow(n, N, MOD)
        for i in range(2, n+1):
            ret -= a(n//i)
        memo[n] = ret
        return ret


ans = 0
for i in range(1, K+1):
    ans += i*a(K//i)
    ans %= MOD
print(ans)

Solution (Python):
def divisor(i):
    cnt = 0
    y = i ** (1 / 2)
    for j in range(1, int(y) + 1):
        if i % j == 0:
            cnt += (x[j] + x[i // j])
    if y % 1 == 0:
        cnt -= x[int(y)]
    return cnt

n, k = map(int, input().split())
mod = pow(10, 9) + 7
ans = 0
x = [0] * (k + 1)
for i in range(1, k + 1):
    x[i] = i - divisor(i)
    ans += (x[i] * (pow(k // i, n, mod)) % mod)
    ans %= 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, 0, -1):
    cnt[i] = (pow(k//i, n, mod) - sum(cnt[2*i:k+1:i])) % mod
    ans = (ans + i*cnt[i]) % mod

print(ans)

Solution (Python):

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

MOD = 10 ** 9 + 7

ctr = [0] * (K + 1)
for n in reversed(range(1, K + 1)):
    ctr[n] = pow(K // n, N, MOD)
    for j in range(2 * n, K + 1, n):
        ctr[n] -= ctr[j]

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

print(ans)

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

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, k = map(int, input().split())
    mod = 10 ** 9+ 7
    table = [0]*(k+1)
    ans= 0
    for i in range(k, 0, -1):
        table[i] = pow(k//i, n, mod)
        j = 2
        while i*j <= k:
            table[i] -= table[i*j]
            table[i] %= mod
            j += 1
        ans += i*table[i]
        ans %= mod
    print(ans)



if __name__ == '__main__':
    main()

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

Solution (Python):



mod=int(1000000007)


def bm(n,p):
    n,p=int(n),int(p)
    if p==0:
        return 1
    x=bm(n,p/2)
    x=(x*x)%mod
    if p%2==1:
        x=(x*n)%mod
    return x

dp=[0]*(100000+2)
ans=0
n,k=map(int,input().split())

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

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

Solution (Python):
class GCD:

    def __init__(self, N, K, MOD):
        self.N = N
        self.K = K
        self.MOD = MOD
        self.gcd_count_list = []
        self.gcd_count_list2 = [0]*self.K
        for d in range(1,self.K+1):
            self.gcd_count_list.append(self.gcd_count(d))
        self.gcd_count2()

    def gcd_count(self, d):
        """  d, 2d, 3d,... の最大公約数を持つ K 以下の整数 N 個の組の数　"""
        return pow(self.K//d,self.N,self.MOD)

    def gcd_count2(self):
        """  dの最大公約数を持つ K 以下の整数 N 個の組の数　"""
        res = []
        i = 1
        while K//i > 0:
            for j in range(K//(i+1)+1,K//i+1):
                self.gcd_count_list2[j-1] = self.gcd_count_list[j-1] \
                - sum(self.gcd_count_list2[j*k-1] for k in range(2, i+1))
            i += 1

    def solve(self):
        return sum(d*self.gcd_count_list2[d-1] for d in range(1,K+1))%MOD

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

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

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

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

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

    return K * x % mod


yaku = [0]*(k+1)
for i in range(1,k+1):
    yaku[i] = k // i
am = [0]*(k+1)
for i in range(1,k+1):
    am[i] = pk(yaku[i],n,MOD)
    
newam = [0]*(k+1)
for i in range(k,0,-1):
    newam[i] = am[i]
    for j in range(i*2,k+1,i):
        newam[i] = ((newam[i] + MOD) - newam[j]) % MOD
        
ans = 0
for i in range(1,k+1):
    ans = (ans + (newam[i]*i)) % MOD
    
print(ans)

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

for i in range(1, K+1)[::-1]:
    num = K // i
    a = pow(num, N, mod)
    for j in range(2, K+1):
        if j * i > K:
            break
        a -= Memo[j * i]
    Memo[i] = a % mod
    ans += a * i
    ans %= mod

print(ans % mod)

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

Solution (Python):
N,K = map(int,input().split())
M = 10 ** 9 + 7
l = [0] * (K + 1)
cnt = 0
for k in range(K,0,-1):
    a = pow(K // k, N, M)
    l[k] = a - sum(l[k*2::k])
for k in range(1,K + 1):
    cnt += k * l[k]
print(cnt % M)

Solution (Python):
[N,K] = list(map(int,input().split()))
S = 0
out = [0]*(K+1)
p = 10**9+7
for i in range(K):
    X = K-i
    out[X] = pow(int(K/X),N,p)
    t=2
    while t*X<=K:
        out[X] = out[X]-out[t*X]
        t+=1
    S = (S + X*out[X])%p
print(S)

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

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


l = [0]*(K+1)
for i in range(1, K+1):
    p = pow(K//i, N, MOD)
    l[i] = p

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

r = 0
for i, l_i in enumerate(l):
    r = (r + (i*l_i) % MOD) % MOD

print(r)

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


cnt = [0] * (K + 1)


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

res = 0
for k in range(K, 0, -1):
    p = 2
    while p * k <= K:
        cnt[k] -= cnt[p * k]
        cnt[k] %= MOD
        p += 1
    res += cnt[k] * k
    res %= MOD

print(res)

Solution (Python):
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10 ** 9 + 7    
N, K = map(int, readline().split())
d = [0] * (K+1)
for i in range(K,0,-1):
    t = K // i
    cnt = pow(t,N,MOD)
    for j in range(2,t+1):
        cnt -= d[i*j]
        cnt %= MOD
    d[i] = cnt
ans = 0
for num,cnt in enumerate(d):
    ans += num * cnt
    ans %= MOD
print(ans)

Solution (Python):
def pow(a, n, mod):
    ret = 1
    pw = a
    while n > 0:
        if n & 1 == 1:
            ret *= pw
            ret %= mod
        n >>= 1
        pw *= pw
        pw %= mod
    return ret


def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    n_gcds = [0 for _ in range(K + 1)]
    for g in range(K, 0, -1):
        v = pow(K // g, N, MOD)
        gg = g
        while gg + g <= K:
            gg += g
            v -= n_gcds[gg]
            v %= MOD
        n_gcds[g] = v
    ans = 0
    for g, n in enumerate(n_gcds):
        ans += g * n
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0
for i in range(K, 0, -1):
    c = pow(K//i, N, P) - sum(cnt[::i])
    cnt[i] = c
    ans = (ans+i*c)%P

print(ans%P)

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


dp = [0]*(k+1)
for i in reversed(range(1, k+1)):
    if not cnt[i]:
        continue
    tmp = cnt[i]
    for j in range(2, k+1):
        if k < i*j:
            break
        tmp -= dp[i*j]
        tmp %= MOD
    dp[i] = tmp

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

print(ans)

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

def power(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

X = [0]*(k+1)
ans = 0
for i in reversed(range(1, k+1)):
    temp = power(k//i, n, mod)
    j = i
    while j <= k:
        temp -= X[j]
        j += i
    ans += temp*i
    ans %= mod
    X[i] = temp
print(ans%mod)

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

Solution (Python):

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

Solution (Python):


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union






























def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    


    def solve(n, k):
        ans = 0
        num_of_total_gcd = [0] * (k + 1)
        for m in range(k, 0, -1):
            cnt = pow(k//m, n, mod)
            for i in range(2, k+1):
                if m * i <= k:
                    cnt -= num_of_total_gcd[m * i]
                else:
                    break
            num_of_total_gcd[m] = cnt % mod
            ans = (ans + m * cnt) % mod
        return ans


    
    n, k = mi()
    print(solve(n, k))


if __name__ == "__main__":
    main()

Solution (Python):
n,k = map(int,input().split())
mod = 1000000007
cnt = [0]*(k+1)
for i in range(1,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 = 0
for i in range(1,k+1):
    ans += cnt[i]*i
    ans %= mod
print(ans)

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

Solution (Python):
n, k = map(int, input().split())
prime_mod = 10**9+7
countgcd = [0]*k
for idx in range(k, 0, -1):
  num_multiples = k//idx
  num_sequences = pow(num_multiples, n, prime_mod)
  overcount = sum(countgcd[j*idx-1] for j in range(2, num_multiples+1))
  overcount = overcount%prime_mod
  countgcd[idx-1] = (num_sequences-overcount)%prime_mod
  
final_sum = 0
for idx in range(1, k+1):
  final_sum = (final_sum + idx*countgcd[idx-1])%prime_mod
print(final_sum)

Solution (Python):
from math import gcd 
N,K=map(int,input().split())

mod=10**9+7

A=[0]*K

for i in range(K,0,-1):
    a=K//i
    b=pow(a,N,mod)
    A[i-1]=b

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

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

print(s)

Solution (Python):

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

if __name__ == "__main__":
    resolve()

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

cnt_l = [0]*(k+1)
MOD = 10**9+7

for i in range(k,0,-1):
    multi_cnt = k//i
    cnt = pow(multi_cnt,n,MOD)
    
    i_multi = i+i
    while i_multi <= k:
        cnt -= cnt_l[i_multi]
        i_multi+=i

    cnt_l[i] = cnt%MOD

ans = 0
for i, cnt in enumerate(cnt_l):
    ans += i*cnt
    ans %= MOD


print(ans)

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

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

Solution (Python):


import sys
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    
    dp=[0]*(K+1)
    MOD=10**9+7
    for i in range(K,0,-1):
        x=(K//i)
        dp[i]=pow(x,N,MOD)
        
        for j in range(2,x+1):
            dp[i]-=dp[i*j]
            dp[i]%=MOD
    ans=0
    for i in range(K+1):
        ans+=i*dp[i]
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

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