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



Sample input:
3 2


Sample output:
9

Submission status: Accepted

Solution code:
import sys
import os

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()

    N,K=map(int, input().split())   #K以下、Nの長さ

    tmp=[0]*(K+1)
    mod=10**9+7
    out=0

    for i in range(K,0,-1):
        tmp[i]=pow(K//i,N,mod)  #iの倍数はK/i個ある。それがN個並んでいる
        for j in range(i*2,K+1,i):
            tmp[i]-=tmp[j]
        out+=tmp[i]*i

    print(out%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def find(N,K):
    MOD = 10**9+7
    number = [1]*(K+1)
    for i in range(K,0,-1):
        number[i] = pow(K//i,N,MOD)
        for j in range(2,K+1):
            if i*j>K:
                break
            number[i] -= number[i*j]
            number[i] %= MOD
    ans = 0
    for k in range(1,K+1):
        ans += number[k]*k
        ans %= MOD
    return ans
N,K = list(map(int,input().strip().split()))
print(find(N,K))

Submission status: Accepted

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

xs = [i for i in range(1, k + 1)]
xs.reverse()

dict_x = {}

mod = 10 ** 9 + 7

def pow(x, y):
    global mod
    a = 1
    b = x
    c = y
    while c > 0:
        if c & 1:
            a = (a * b) % mod
        b = (b * b) % mod
        c = c >> 1
    return a

answer = 0
for x in xs:
    num = k // x
    a = pow(num, n)
    # print(a)
    s = 2
    while x * s <= k:
        a -= dict_x[x * s]
        s += 1
    dict_x[x] = a
    answer = (answer + a * x) % mod

print(answer)

Submission status: Accepted

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

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

cnt = 0
for i , c in enumerate( Cnt ):
  cnt += i * c
  cnt = cnt % mod 

print( cnt )

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
g = [1] * k
mod = 10 ** 9 + 7

for i in range(k, 0, -1):
    x = k // i
    m = n
    while m > 0:
        if m & 1:
            g[i-1] = g[i-1] * x % mod
        x = x * x % mod
        m >>= 1

    y = 2
    while i * y <= k:
        g[i-1] -= g[i*y-1]
        y += 1

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

print(ans)

Submission status: Accepted

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

ans = 0
memo = [0] * (K + 1)
for i in range(K, 0, -1):
    x = K // i
    cnt = pow(x, N, mod)

    a = i
    while a <= K:
        cnt -= memo[a]
        a += i

    memo[i] = cnt
    ans += i * cnt
    ans %= mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def powmod(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 = (n - 1) // 2
   else:
    x = x ** 2%mod
    n = n // 2%mod
  return K * x # 指数を割り続け n が 1 に至ったら終了
N,K = map(int,input().split())
mod=10**9+7
ans=[0]*(K+1)
for i in range(K):
 b=int(K/(K-i))
 if b==1:
  ans[K-i]+=1
 else:
  ans[K-i]+=powmod(b, N,mod)
  ans[K-i]%=mod
  for j in range(b-1):
   ans[K-i]-= ans[(K-i)*(j+2)]
   ans[K-i]%=mod
c=0
for i in range(K+1):
 c+=ans[i]*i
 c%=mod
print(c)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
mod = 10 ** 9 + 7
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)

Submission status: Accepted

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

mod = 10**9+7

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )
n,k = map(int, input().split())
ansls = [mint(0) for _ in range(k+1)]

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
INF = 10 ** 18

def divisors(n) -> list:
    res = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
    return res


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

cnt = defaultdict(int)
for k in range(1, K + 1):
    for d in divisors(k):
        cnt[d] += 1
#print(cnt)

tmp = defaultdict(int)
for k in range(K, 0, -1):
    tmp[k] = pow(cnt[k], N, MOD)
    for i in range(2, K // k + 1):
        tmp[k] -= tmp[i * k]
#print(tmp)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, K: int):
    num_gcd = {}
    for k in range(K, 0, -1):
        num_select = K // k
        num_gcd_k = pow(num_select, N, MOD)
        for multiple in range(2, num_select+1):
            num_gcd_k -= num_gcd[k * multiple]
        num_gcd[k] = num_gcd_k

    result = 0
    for k in range(1, K+1):
        result += (k * num_gcd[k]) % MOD
    print(result % MOD)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

# すべての要素がiの倍数であるような数列の数
# 後ろから確定して引いていく。前からだと重複が入ってあとから引きづらくなる
m = [0] * (K+1)
for i in range(K, 0, -1):
    m[i] = pow(K//i, N, mod)
    j = 2
    while True:
        if i * j > K:
            break
        m[i] -= m[i*j]
        j += 1

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, read().split())
mod = 10 ** 9 + 7
memo = [0] * (k + 1)
ans = 0
for x in range(k, 0, -1):
    v = k // x
    tmp = pow(v, n, mod)
    for i in range(2, v + 1):
        tmp -= memo[i * x]
        tmp %= mod
    memo[x] = tmp
for i, vv in enumerate(memo):
    ans += i * vv
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
mod = 10**9+7
gcd = [0]*(k+1)#gcdがiとなるようなものの個数
ans = 0
for i in range(k,0,-1):
    tmp = pow(k//i,n,mod)
    for j in range(i*2,k+1,i):
        tmp -= gcd[j]
    gcd[i] = tmp
    ans += tmp*i
    ans %=mod
print(ans)

Submission status: Accepted

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

bin=list(str(format(n,'b')))

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

for i in reversed(range(1,k+1)):
  p=k//i
  pn=[p]
  for x in range(len(bin)-1):
    y=pn[x]**2%mod
    pn.append(y)
  num=1
  for l in range(len(bin)):
    if bin[l]=='1':
      num=num*pn[-1-l]%mod
  j=2
  while i*j<=k:
    num=(num-list[i*j])%mod
    j=j+1
  list[i]=num
  ans=(ans+num*i)%mod
print(ans)

Submission status: Accepted

Solution code:

mod = pow(10, 9) + 7

def main():
    N, K = map(int, input().split())
    table = [0]*(K+1)
    for k in range(K, 0, -1):
        m = K//k
        tmp = pow(m, N, mod)
        for l in range(2, m+1):
            tmp -= table[l*k]
            tmp %= mod
        table[k] = tmp

    ans = 0
    for i in range(len(table)):
        ans += (i * table[i])%mod
    ans %= mod
    #print(table)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 解説AC
mod = 10 ** 9 + 7
n, k = map(int, input().split())
dp = [-1] * (k + 1)
ans = 0
for i in range(k, 0, -1):
    dp[i] = pow(k // i, n, mod)
    t = 0
    t += 2 * i
    while t <= k:
        dp[i] -= dp[t]
        dp[i] %= mod
        t += i
    ans += i * dp[i]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
lst = [0] + [pow(K // d, N, MOD) for d in range(1, K + 1)]

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

ans = 0
for i, x in enumerate(lst):
    ans = (ans + i * x) % MOD
print(ans)

Submission status: Accepted

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


#%%
ans = 0
gcds = [0]*(K+1)
for i in reversed(range(1, K+1)):
    gcds[i] = pow(K//i, N, MOD)
    idx = i*2
    while idx<K+1:
        gcds[i] -= gcds[idx] + MOD
        gcds[i] %= MOD
        idx += i
    ans += (i * gcds[i])
    ans %= MOD


print(ans)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
numgcd = [0]*(K+1)
sumgcd = 0
mod = 10**9+7
for i in range(1, K+1)[::-1]:
    numgcd[i] = pow(K//i, N, mod)
    count = 2
    while count*i <= K:
        numgcd[i] -= numgcd[count*i]
        count += 1
    sumgcd += numgcd[i]*i
print(sumgcd%mod)

Submission status: Accepted

Solution code:
def left_bin(a, n, c):
    ns = [int(i) for i in bin(n)[3:]]
    t = a
    for i in ns:
        t = t*t % c
        if i == 1:
            t = t*a % c
    return t


n, k = map(int, input().split())
c = 10**9+7
tm = [0] + [1]*k
a = k//2
ans = k*(k+1)//2 - a*(a+1)//2
for i in range(k//2, 0, -1):
    a = k//i
    t = (left_bin(a, n, c) - sum([tm[j*i] for j in range(2, a+1)])) % c
    ans = (ans + t*i) % c
    tm[i] = t
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
def mod_pow(p, q):
    res = 1
    while q > 0:
        if q & 1:
            res = (res * p) % MOD
        q //= 2
        p = (p * p) % MOD
    return res

def solve(n, k):
    dp = [0] * (k+1)
    ans = 0
    for x in range(k, 0, -1):
        dp[x] = mod_pow((k // x), n) - sum(dp[y] for y in range(2*x, k+1, x))
        dp[x] %= MOD
        ans += dp[x] * x
    return ans % MOD

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

Submission status: Accepted

Solution code:
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(i, k+1):
    ans += d[i] * i

ans %= mod
print (ans)

Submission status: Accepted

Solution code:
def POW(x, n, mod): #xのn乗をmodで割った際の余りの高速計算
    ans = 1
    while n > 0:
        if n % 2 == 1:
            ans *= x%mod
        x = (x*x)%mod
        n >>= 1						#ビットシフト
    return ans

if __name__ == '__main__':
	N, K = map(int, input().split())
	lst = [0] * (K+1)
	mod = 10 ** 9 + 7

	ans = 0

	for i in range(K):
		k = K - i
		n = K // k
		v = POW(n,N,mod)
		m = 2
		while(m * k <= K):
			v -= lst[m*k]
			if v < 0:
				v += mod
			m += 1
		lst[k] = v
		v = (k * v)%mod
		ans = (ans+v)%mod

	print(int(ans))

Submission status: Accepted

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

B=[0 for i in range(K+1)]
for i in range(K+1)[::-1]:
    if i==0: continue
    B[i]=pow((K//i),N,MOD)
    t=i*2
    while t<=K:
        B[i]-=B[t]
        t+=i

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

Submission status: Accepted

Solution code:
import sys
input=lambda :sys.stdin.readline().rstrip()

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

Submission status: Accepted

Solution code:
mod = 10**9 + 7
n,k= [int(i) for i in 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 idx,i in enumerate(d):
    ans += (idx) * i
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict

N,K = map(int,input().split())
mod = 10**9+7
DP = [0]*(K+1)  #DP[i]:gcd=iとなる数列の個数
ans = 0

for i in range(K,0,-1):
    m = K//i    #m:iの倍数の個数
    DP[i] = pow(m,N,mod)
    for j in range(2,m+1):
        DP[i] -= DP[i*j]
    ans += (DP[i]*i) % mod
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
# 1以上k以下の整数がn個
mod=int(1e+9 + 7)
d=[0]*(k+1)
ans=0
for i in range(k,0,-1):
      m=k//i
      d[i]=pow(m,n, mod) 
      d[i]-=sum([d[j*i]for j in range(2,m+1)])
      ans+=(d[i]*i)%mod
print((ans)%mod)
#print(d)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
m=1000000007
ans=0
dp=[0]*(k+1) #dp[i]:=iを数列内の最大値とするもののgcd合計
for i in range(k,0,-1):
  mul_i=k//i#iの倍数の個数
  dp[i]=pow(mul_i,n,m)
  for j in range(2,mul_i+1):
    dp[i]=(m+dp[i]-dp[i*j])%m
  ans+=i*dp[i]%m
ans%=m
print(ans)

Submission status: Accepted

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

data = [0]*(K+1)
for x in range(K,0,-1):
    p = pow(K//x,N,mod)
    for k in range(2,K//x+1):
        p -= data[k*x]
        p %= mod
    data[x] = p
    ans += x*p
    ans %= mod

###
#print(data)
###
    
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
gcds = np.zeros((K + 1,), dtype=np.int64)
for n in range(K, 0, -1):
    gcds[n] = (pow(K // n, N, MOD) - gcds[np.arange(1, K // n + 1, dtype=np.int64) * n].sum()) % MOD
print(gcds @ np.arange(K + 1, dtype=np.int64) % MOD)

Submission status: Accepted

Solution code:
import numpy as np
MOD = 10 ** 9 + 7
N, K = map(int, input().split())
gcds = np.zeros((K + 1,), dtype=np.int64)
for n in range(K, 0, -1):
    gcds[n] = (pow(K // n, N, MOD) - gcds[np.arange(1, K // n + 1, dtype=np.int64) * n].sum()) % MOD
print(gcds @ np.arange(K + 1) % MOD)

Submission status: Accepted

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

Submission status: Accepted

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

s = [0] * (k + 1)
ans = 0

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

for i in range(1, k+1):
    ans += i * s[i]
    ans %= 1e9 + 7

ans %= 1e9+7

print(int(ans))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10 ** 9 + 7
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(i * 2, 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)

Submission status: Accepted

Solution code:
N, K = [int(n) for n in input().split()]
NUM = 1000000007

def modpow(a, b): # (a ** b) % NUM
    ans = 1
    while b != 0:
        if b % 2 == 1:
            ans *= a
            ans %= NUM
        a = a * a
        a %= NUM
        b //= 2
    return ans

C = [0 for _ in range(K+1)]
for d in range(K):
    k = K - d # K ... 1
    L = K // k
    C[k] = modpow(L, N) # A = 1*k ... L*k
    for l in range(2, L+1):
        C[k] -= C[l*k]
        if C[k] < 0:
            C[k] += NUM
        C[k] %= NUM

ans = 0
for k in range(1, K+1):
    ans += k * C[k]
    ans %= NUM
print(ans)

Submission status: Accepted

Solution code:
def examA():
    N = SI()
    ans = "No"
    for s in N:
        if s=="7":
            ans = "Yes"
    print(ans)
    return

def examB():
    N = I()
    ans = 0
    for i in range(1,N+1):
        if i%3==0:
            continue
        if i%5==0:
            continue
        ans += i
    print(ans)
    return

def examC():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x
    K = I()
    ans = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            cur = gcd(i,j)
            for k in range(1,K+1):
                ans += gcd(cur,k)
    print(ans)
    return

def examD():
    N = I()
    S = SI()
    R = [0]*(N+1)
    G = [0]*(N+1)
    B = [0]*(N+1)
    for i in range(N):
        s = S[i]
        R[i+1] += R[i]
        G[i+1] += G[i]
        B[i+1] += B[i]
        if s=="R":
            R[i+1] += 1
        elif s=="G":
            G[i+1] += 1
        elif s=="B":
            B[i+1] += 1
    ans = 0
    for l in range(N):
        Ls = S[l]
        for r in range(l+3,N):
            Rs = S[r]
            if (Ls=="R" and Rs=="B") or (Ls=="B" and Rs=="R"):
                ans += G[r] - G[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="G":
                        ans -= 1
            elif (Ls=="R" and Rs=="G") or (Ls=="G" and Rs=="R"):
                ans += B[r] - B[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="B":
                        ans -= 1
            elif (Ls=="G" and Rs=="B") or (Ls=="B" and Rs=="G"):
                ans += R[r] - R[l]
                if (l+r)%2==0:
                    if S[(l+r)//2]=="R":
                        ans -= 1
    print(ans)
    return

def examE():
    N, K = LI()
    G = [0]*(K+1)
    ans = 0
    for i in range(K,0,-1):
        g = pow(K//i,N,mod)
        for l in range(2,(K//i)+1):
            g -= G[i*l]
            if g<0:
                g += mod
        G[i] = g
        ans += g*i
        ans %= mod
    print(ans)
    #print(G)
    return

def examF():
    N = I()
    A = LI()

    if N%2==0:
        O = [0] * N
        E = [0] * N
        for i in range(N):
            O[i] += O[i - 1]
            E[i] += E[i - 1]
            if i % 2 == 0:
                O[i] += A[i]
            else:
                E[i] += A[i]
        #print(O,E)
        ans = max(O[-1],E[-1])
        print(ans)
        return

    def dfs(n,k):
        if (n+2)//2 <k:
            return -inf
        if k == 0:
            return 0
        if n==0:
            if k==1:
                return A[0]
            return -inf
        if n==1:
            if k==1:
                return max(A[0],A[1])
            return -inf
        res = max(A[n]+dfs(n-2,k-1),dfs(n-1,k))
        return res

    ans = dfs(N-1,N//2)
    #print(dfs(4,2))
    print(ans)
    return

def examF2():
    N = I()
    A = LI()

    dp = [[-inf]*3 for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 0
    dp[0][2] = 0
    dp[1][0] = -inf
    dp[1][1] = 0
    dp[1][2] = A[0]
    for i in range(1,N):
        dp[i+1][2] = A[i] + dp[i-1][2]
        dp[i+1][1] = max(A[i] + dp[i-1][1],dp[i][2])
        dp[i+1][0] = max(A[i] + dp[i-1][0],dp[i][1])
    if N%2==1:
        ans = max(dp[-1][0],dp[-1][1])
    else:
        ans = max(dp[-1][1],dp[-1][2])
    #print(dp)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
27
18 18 19 28 -45 90 -45 23 -53 60 28 -74 -71 35 -26 -62 49 -77 57 24 -70 -93 69 -99 59 57 -49
"""

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
p = 10**9+7
F = {}
s = 0
for i in range(k, 0, -1):
    F[i] = pow(k//i, n, p)
    for j in range(2*i, k+1, i):
        F[i] -= F[j]
    s = (s + F[i] * i) % p
print(s)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
dlist=[[]for i in range(k+1)]
mod = 10**9+7
num=[0]*(k+1)
idx=0
for i in range(1,k+1):
    num[i]=pow(k//i,n,mod)
    for p in range(i*2,k+1,i):
        dlist[p].append(i)
for i in range(k,0,-1):
    for d in dlist[i]:
        num[d]=(num[d]-num[i])%mod
print(sum([i*x for i,x in enumerate(num)])%mod)

Submission status: Accepted

Solution code:
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]

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

Submission status: Accepted

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

for x in range(K,0,-1):
    l[x]=pow((K//x),N,mod)
    for y in range(2*x,K+1,x):
        l[x]-=l[y]
        l[x]=pow(l[x],1,mod)
    ans+=l[x]*x
    ans=pow(ans,1,mod)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# countBcd[i] : 最大公約数がiとなる数列の個数
# 全てiの倍数である数列の数はint(K/i) ** N ただし、全てi*2,i*3・・・の場合を除く

N, K = [int(x) for x in input().split()]
countBcd = [0]*(K+1)
mod=10**9+7
sumTotal=0
for i in range(K,0,-1):
    countBcd[i] = pow(K//i,N,mod)

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

    sumTotal += i*countBcd[i]%mod

print(sumTotal%mod)

Submission status: Accepted

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

def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

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

print(ans%mod)

Submission status: Accepted

Solution code:
mod=10**9+7
N,K=map(int,input().split())
d=[0]*(K+1)
ans=0
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+=d[i]*i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
import sys
input = sys.stdin.readline

mod = 1000000007


def fpow(x, power, mod):
    x %= mod
    ans = 1
    while power != 0:
        if (power & 1) == 1:
            ans = ans * x % mod
        power >>= 1
        x = x * x % mod
    return ans


def fac(x):
    A = []
    i = 1
    while i * i <= x:
        if x % i == 0:
            A.append(i)
            if (x // i) != i:
                A.append(x // i)
        i += 1
    return A


n, k = map(int, input().split())
ans = 0
# print(fpow(n,k,mod))
A = [0] * (k + 2)
ans = 0
for i in range(k, 0, -1):
    #print(i,A[i],fpow(k // i, n, mod))
    A[i] += fpow(k // i, n, mod)
    while A[i] < 0:
        A[i] += mod
    A[i] %= mod
    ans = ans + A[i] * i
    ans %= mod
    B = fac(i)
    for b in B:
        if b!=i:
            A[b] -= A[i]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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


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

print(ans%mod)

Submission status: Accepted

Solution code:
MOD = 1000000007
N, K = map(int, input().split())
ans = 0
f = [0] * (K+1)
g = [0] * (K+1)
for t in range(K, 0, -1):
    f[t] = pow(K//t, N, MOD)
    g[t] = f[t]
    for s in range(2 * t, K+1, t):
        g[t] -= g[s]
    ans = (ans + t * g[t]) % MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def modpow(a, b, mod):
    ret = 1
    while b > 0:
        if b % 2 == 1:
            ret = ret * a % mod
        a = a * a % mod
        b //= 2
    return ret


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

Submission status: Accepted

Solution code:
MOD = 1000000007

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

Submission status: Accepted

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

MOD = 10**9+7

# process
l = [0]*(K+1)  # 最大公約数がiとなる数列の数
ans = 0
for i in range(K, 0, -1):
    l[i] = pow((K//i), N, MOD) - sum(l[i*j] for j in range(2, K//i+1)) % MOD
    ans = (ans + i*l[i]) % MOD

# output
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 10**9+7
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 += i*d[i] % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = 1000000007
ans = 0
c = {}
for i in range(k, 0, -1):
    t = pow(k // i, n, MOD)
    m = 2
    while i * m <= k:
        t -= c[i * m]
        m += 1
    c[i] = t % MOD
print(sum([k * v for k, v in c.items()]) % MOD)