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):
def divisor(x):
    div = []
    for i in range(1,int(x**0.5)+1):
        if x%i == 0:
            div.append(i)
            if x != i**2: div.append(x//i)
    
    return div

MOD = 1000000000 + 7

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

count = [0] * k

for i in range(k):
    count[i] = pow(k//(i+1),n,MOD)
    
for i in range(k,0,-1):
    for j in divisor(i):
        if j<i:
            count[j-1] -= count[i-1]
            count[j-1] %= MOD

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

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

MOD = 1000000007

def smax(a,b):
    if a>b:
        return a
    else:
        return b

def smin(a,b):
    if a<b:
        return a
    else:
        return b


def main():
    N,K = list(map(int,readline().split()))
    DP = [0]*(K+1)
    ans = 0
    pow_list = [pow(i,N,MOD) for i in range(1,K+1)]
    for i in range(K):
        x = K-i
        DP[x] = pow_list[int(K/x)-1]
    
    for s in range(K):
        i = K-s
        x = int(K/i)
        
        val = DP[i]
        
        for j in range(1,x):
            val += MOD - DP[i*(j+1)]
            val %= MOD
            """
            if checked[j]==False:
                ans += MOD - (DP[i*(j+1)]*i)%MOD
                ans %= MOD
                
                k = j+1
                while k < x+1:
                    if checked[k-1]:
                        print(k)
                        ans += DP[i*k]*i
                        ans %= MOD
                    checked[k-1] = True
                    k += j+1
            """
        ans += val*i
        ans %= MOD
        DP[i] = val
    print(ans)
        

if __name__ == '__main__':
    main()

Solution (Python):

import sys

MOD = 1000000007  


def solve(N: int, K: int):
    count = [0]*(K+1)

    answer = 0
    for k in range(K,0,-1): 
        d = K//k
        if k == 1:
            answer += pow(K,N,MOD)-sum(count) 
        else:
            count[k] = pow(d,N,MOD)
            i = 2
            while k*i <= K:
                count[k] -= count[k*i]
                i += 1
            answer += count[k]*k
        answer %= MOD
    print(answer)
    return


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

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import functools
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  


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

    def NN(a):
        return K//a

    @functools.lru_cache(maxsize=None)
    def f(a):
        ans = pow(NN(a), N, MOD)
        for i in range(2, K+1):
            if i*a > K:
                break
            ans -= f(i*a)
            ans %= MOD
        return ans % MOD

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

    return


def main():

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


if __name__ == '__main__':
    main()

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

dp = [1] * (K+1)
for n in range(K//2,0,-1):
    p = pow(K//n,N,MOD)
    for m in range(2*n,K+1,n):
        p -= dp[m]
    dp[n] = p%MOD

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

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

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

mod = 10 ** 9 + 7

def make_divisors(N) :
  divisors = []
  for i in range(1, N + 1) :
    if i * i > N :
      break
    if N % i == 0:
      divisors.append(i)
      if i != N // i:
        divisors.append(N // i)

  return divisors

cnt = [0] * (K + 1)

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

print(ret)

Solution (Python):
n,k = map(int,input().split())
ans = 0
dev = [[] for _ in range(k+1)]
for i in range(1,k+1):
  l = int(i**.5)
  for j in range(1,l+1):
    if i % j == 0:
      dev[i].append(j)
      dev[i].append(i // j)
  if l**2 == i:
    dev[i].pop()
  

cnt = [0 for _ in range(k+1)]
mod = 10 ** 9 + 7
for d in range(1,k+1):
  p = k // d
  double = [p]
  now = 1
  for i in range(20):
    double.append(double[-1]**2%mod)
  
  m = int(n)
  i = 0
  while m:
    if m % 2 != 0:
      now *= double[i]
    m //= 2
    i += 1
  
  cnt[d] = now

for i in range(1,k+1)[::-1]:
  for x in dev[i]:
    if x != i:
      cnt[x] -= cnt[i]

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

print(ans)

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

yakusu = [0]
ans = 0
for i in range(K):
    n = i + 1

    yaku = 0
    if n > 1:
        for j in range(1, int(n**0.5)+1):
            if n % j == 0:
                yaku += j - yakusu[j]
                if j != n//j and j != 1:
                    yaku += n//j - yakusu[n//j]
    yakusu.append(yaku)

    ans += pow((K//n), N, MOD) * (n - yaku)
    ans %= MOD

print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod = 10**9 + 7

n, k = nm()
rl = [-1]*(k+1)
dp = [0]*(k+1)
ans = 0
for i in range(k, 0, -1):
    t = k//i
    if rl[t] < 0:
        rl[t] = pow(t, n, mod)
    r = rl[t]
    for j in range(2*i, k+1, i):
        r = (r - dp[j]) % mod
    dp[i] = r
    ans = (ans + r*i) % mod
print(ans)

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

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

P = 10 ** 9 + 7

def mod_prod(a,b):
    return a * b % P

def mod_fact(a):
    ret = 1
    for i in range(a):
        ret = ret * (i + 1) % P
    return ret

def mod_pow(a, n):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * a % P
        a = a * a % P
        n = n // 2
    return ret

def mod_div(a, b):
    b_inv = mod_pow(b, P - 2)
    return a * b_inv % P

def mod_comb(a,b):
    ret = 1
    b = min(b, a - b)
    for i in range(b):
        ret *= a - i
        ret %= P
    ret = mod_div(ret, mod_fact(b))
    return ret


a = [0] * (K + 1)
a[-1] = 1

for i in range(K - 1, 0, -1):
    x = K // i
    x = mod_pow(x, N)
    for j in range(i * 2, K + 1, i):
        x -= a[j]
    a[i] = x % P

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

print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd

sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])


def f(dp,n,k):
    if dp[k] != -1:
        return dp[k]
    if k == 1:
        return 1
    cnt = 0
    cnt = pow(k,n,mod)
    for i in range(2,k+1):
        cnt += mod
        cnt -= f(dp,n,k//i) 
        cnt %= mod
    dp[k] = cnt       
    return cnt

def main():
    n,k = inpm()
    ans = 0
    dp = [-1 for _ in range(k+1)]
    for e in range(1,k+1):
        ans += e*f(dp,n,k//e)
        ans %= mod
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import math



def modPow(a, n, p):
    if n == 1:
        return a
    if n % 2 == 1:
        return (a * (modPow(a, n // 2, p) ** 2)) % p
    else:
        return (modPow(a, n // 2, p) ** 2) % p


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

ans_array = [0] * (N + 1)
mod = 10 ** 9 + 7

for i in range(N, 0, -1):
    c = N // i
    ans_array[i] = (ans_array[i] + modPow(c, K, mod)) % mod
    if i != 1:
        ans_array[1] = (ans_array[1] - ans_array[i] + mod) % mod
    for j in range(2, int(math.sqrt(i) + 1)):
        if i % j == 0:
            if i == j * j:
                ans_array[j] = (ans_array[j] - ans_array[i] + mod) % mod
                break
            else:
                ans_array[j] = (ans_array[j] - ans_array[i] + mod) % mod
                ans_array[i // j] = (ans_array[i // j] -
                                     ans_array[i] + mod) % mod

ans = 0

for i, v in enumerate(ans_array):
    ans = (ans + i * v) % mod

print(ans)

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

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

memo = {1:1}
def f(k):
    if k in memo:
        return memo[k]
    res = pow(k,N,MOD)
    for i in range(2,k+1):
        res -= f(k//i)
    res = res % MOD
    memo[k] = res
    return res

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

print(ans)

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

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

for i in range(1, k+1):
    m = i - count[i]
    ans += pow(k//i, n, mod) * m
    ans %= mod
    for j in range(i, k+1, i):
        count[j] += m

print(ans)

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

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

A = [0] + [k//i for i in range(1, k+1)]
B = list(set(A))

D = {}
for i in B:
    D[i] = pow(i, n, mod)



ans = [0] * (k+1)
for i in range(k, 0, -1):
    ans[i] = D[A[i]] % mod
    
    ii = i * 2
    while ii <= k:
        
        ans[i] = (ans[i] - ans[ii]) % mod
        ii += i



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

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

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

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
mod = 10 ** 9 + 7
table = [0] * (K + 1)
table[1] = K
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors
for i in range(2, K + 1): table[i] = (K // i) % mod
res = 0
tt = [0] * (K + 1)
for i in range(K, 0, -1):
  t = pow(table[i], N, mod) + tt[i]
  divs = make_divisors(i)
  
  for d in divs:
    if d < i: tt[d] -= t
  res += t * i % mod
  res %= mod
  
print(res)

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


def main():
    n, k = map(int, input().split())

    baisuu = [[] for _ in [0]*(k+1)]
    tree = [0]*(k+1)

    for i in range(1, k+1):
        j = 2*i
        while j <= k:
            baisuu[i] += [j]
            j += i
        tree[i] = pow(len(baisuu[i])+1, n, mod)
    for i in range(k, 0, -1):
        for j in baisuu[i]:
            tree[i] -= tree[j]
        tree[i] %= mod
    ans = 0
    for i, j in enumerate(tree):
        ans = (ans+i*j) % mod
    print(ans)


main()

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

Solution (Python):
def cmb(n,r,mod):
  if r<0 or r>n:
    return 0
  r=min(r,n-r)
  return g1[n]*g2[r]*g2[n-r]%mod

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

g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n+1):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

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

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r]
N, K = map(int, input().split())
B = [0] * (K+1)
r = 0
for i in range(K, 0, -1):
    ac = K//i
    c = power(ac, N)
    bsum = 0
    for j in range(ac-1):
        j += 2
        bsum += B[i*j]
    B[i] = (c - bsum)%mod
    r = (r+B[i]*i)%mod
print(r)

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

for i in range(K, 0, -1):
    a = pow(K//i, N, MOD)
    c = 2
    
    while True:
        if c*i>K:
            break
        
        a -= cnt[c*i]
        a %= MOD
        c += 1
    
    cnt[i] = a
    ans += i*a
    ans %= MOD
    s -= a
    s %= MOD

ans += s

print(ans%MOD)

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

a = [1] * (k+1)
b = [ i for i in range(k+1) ]
a[0] = 0
b[0] = 0

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




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

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,K=MI()
    
    
    cnt=[0]*(K+1)
    
    for i in range(1,K+1):
        aa=K//i
        cnt[i]=pow(aa,N,mod)
        
    for i in range(K,0,-1):
        pn=-1
        for j in range(2*i,K+1,i):
            
            cnt[i]+=cnt[j]*pn
            
    
    ans=0
    for i in range(1,K+1):
        ans+=(i*cnt[i])%mod
        ans%=mod
        
    print(ans)
    

main()

Solution (Python):
from collections import defaultdict
import os
from functools import reduce

import itertools
import sys
from math import gcd

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N, K = list(map(int, sys.stdin.buffer.readline().split()))


def test(N, K):
    s = 0
    counts = defaultdict(int)
    for nums in itertools.product(range(1, K + 1), repeat=N):
        s += reduce(gcd, nums)
        counts[reduce(gcd, nums)] += 1
    print(counts)
    print(s % MOD)









def count_patterns(n):
    
    return pow(K // n, N, MOD)


counts = [0] * (K + 1)
for n in range(1, K + 1):
    cnt = count_patterns(n)
    counts[n] = cnt
for n in reversed(range(1, K + 1)):
    i = n * 2
    while i <= K:
        counts[n] -= counts[i]
        i += n


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

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

mod=10**9+7    
n,k=map(int,input().split())
cnt=[0]*(k+1)
for i in range(k,1,-1):
    divs=divisors(i)
    cnt[i]+=pow(k//i,n,mod)
    for val in divs:
        if val==i:
            continue
        else:
            cnt[val]-=cnt[i]
cnt[1]+=pow(k,n,mod)
ans=0
for i in range(1,k+1):
    ans+=i*(cnt[i])%mod
    ans%=mod
print(ans)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

mod = 10**9 + 7

n, k = nm()
rl = [-1]*(k+1)
dp = [0]*(k+1)
ans = 0
for i in range(k, 0, -1):
    t = k//i
    if rl[t] < 0:
        rl[t] = pow(t, n, mod)
    r = rl[t]
    for j in range(2*i, k+1, i):
        r = (r - dp[j]) % mod
    dp[i] = r
    ans = (ans + r*i) % mod
print(ans)

Solution (Python):
class modpow:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res

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

D = [0] * (K + 1)
ans = 0
mp = modpow(MOD)
for i in range(K, 0, -1):
  t = K // i
  u = mp.modpow(t, N)
  for j in range(i + i, K + 1, i):
    u -= D[j]
  while (u < 0):
    u += MOD
  ans = (ans + u * i) % MOD
  D[i] = u
print(ans)

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

ans = 0
cnt = 0
gs = dict()
for i in range(K,1,-1):
    n = pow(K//i,N,mod)
    for j in range(2,K+1):
        if i*j > K: break
        n -= gs[i*j]
        n %= mod
    gs[i] = n
    ans += n*i%mod
    ans %= mod
    cnt += n
    cnt %= mod
ans += pow(K,N,mod) - cnt
ans %= mod
print(ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



def make_divisors(n,sort=False):
    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)
    if sort:
        divisors.sort()
    return divisors

N,K = LI()

numl = [0]*(K+1)

ans = 0
for i in range(1,K+1)[::-1]:
    num = pow(math.floor(K/i),N,mod)
    for j in range(2*i,K+1,i):
        num -= numl[j]
        num %= mod
    numl[i] = num
    ans += num*i
    ans %= mod

print(ans)

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

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

print(ans)

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

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

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 10**9 + 7

def 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(reverse=True)
    return divisors

n, k = map(int, input().split())
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):
    div = divisors(i)
    base = cnt[i]
    for d in div[1:]:
        cnt[d] -= base
ans = 0
for i, item in enumerate(cnt):
    ans += i * item
    ans %= MOD
print(ans)

Solution (Python):
from math import gcd
from functools import reduce

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

mod=10**9+7

ar=list(range(1,k+1))
ar.reverse()

ans=[0]*(k+1)
for i in ar:
	ava=(k-i)//i+1
	ans[i]=pow(ava,n,mod)
	for j in range(i*2,k+1,i):
		ans[i]-=ans[j]
sum=0
for i,z in enumerate(ans):
	sum+=i*z
print(sum%mod)

Solution (Python):
n, k = map(int, input().split())
mod = 10**9+7
dp = [0]*(k+1)
ans = 0
for i in range(1, k+1)[::-1]:
    res = pow(k//i, n, mod)
    for j in range(i*2, k+1, i):
        res-=dp[j]
    dp[i] = res%mod
    ans+=i*res
    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(1, K+1):
    f = i - cnt[i]
    ans = (ans + f * pow(K//i, N, mod)) % mod
    for j in range(2*i, K+1, i):
        cnt[j] += f
print(ans)

Solution (Python):
N,K=map(int,input().split())
pr=10**9+7
a=0
l=[None]*(K+1)
for i in range(K,0,-1):
    t=pow(K//i,N,pr)
    c=i*2
    while c<=K:
        t-=l[c]
        c+=i
    l[i]=t
    a=(a+t*i)%pr
print(a)

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

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

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

    div_list = [[] for _ in range(K+1)]
    for d in range(1, K+1):
        for i in range(2, K+1):
            if d*i > K:
                break
            div_list[d*i].append(d)

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


if __name__ == '__main__':
    main()

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

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

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

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

ANS=0
for i in range(1,K+1):
    ANS=(ANS+pow(K//i,N,mod)*L[i])%mod

print(ANS)

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

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

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

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

ANS=0
for i in range(1,K+1):
    ANS=(ANS+pow(K//i,N,mod)*L[i])%mod

print(ANS)

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

mod = 10**9+7

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

ans = 0
dp = [None]*(K+1)
for n in reversed(range(1, K+1)):
    L = K//n
    p = pow(L, N, mod)
    for i in range(2, L+1):
        p = (p - dp[n*i]) % mod
    
    dp[n] = p
    ans = (ans + p*n) % mod

print(ans)

Solution (Python):

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

mod = 10**9+7

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

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

    now = pow(K // i,N,mod)

    for j in range(2*i,K+1,i):

        now -= ans[j]
        now %= mod

    ans[i] = now % mod
    ss += i * now
    ss %= mod

    
print (ss)

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

ans = 0
cnt = [0] * (k + 1)
for num in range(1, k + 1)[::-1]:
    cnt[num] = pow((k // num), n, MOD)
    tmp = 2 * num
    while True:
        if tmp >= k + 1:
            break
        cnt[num] -= cnt[tmp]
        cnt[num] % MOD
        tmp += num
        
for num in range(1, k + 1):
    ans += cnt[num] * num
    ans %= MOD
print(ans % MOD)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

def Eratosthenes(N): 
    N+=1
    is_prime_list = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]




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

MOD = 10**9+7
res = [0]+[pow(k//i,n,MOD) for i in range(1,k+1)]

p = Eratosthenes(k)


for i in p:
    for j in range(i,k+1,i):
        res[j//i] -= res[j]


print(sum(ri*i for i,ri in enumerate(res))%MOD)

Solution (Python):
def gcd(x,y):
    while(y): 
        x, y = y, x % y 
    return x
    
MOD = 10 ** 9 + 7

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

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

for i in range(1, K + 1):
    count = K//i
    out += val[i] * pow(count, N, MOD)
    out %= MOD
print(out)

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):
from math import gcd
MOD = 10**9+7
n, k = map(int, input().split())
ans = [0 for _ in range(k+1)]
for i in range(k, 0, -1):
	tmp = pow(k//i, n, MOD)
	for j in range(2*i, k+1, i):
		tmp -= ans[j]
		tmp %= MOD
	ans[i] = tmp

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

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

ans = 0
b = [0]*(k+1)
for i in reversed(range(1, k + 1)):
    c = a[i]
    for j in range(i + i, k + 1, i):
        c -= b[j]
    c %= mod
    b[i] = c
    ans += c * i
    ans %= mod
print(ans)

Solution (Python):
def main():
    mod=1000000007
    n,k=map(int,input().split())
    A=[0]*(k+1)
    A[k]=1
    for i in range(1,k)[::-1]:
        l=k//i
        A[i]=pow(l,n,mod)
        for j in range(2,l+1):
            
            A[i]-=A[i*j]
            A[i]%=mod
    
    ans=0
    for i in range(1,k+1):
        ans+=A[i]*i
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, K = na()
mod = 1000000007

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[j]
        j += i
    if a[i] < 0:
        a[i] %= mod
        if a[i] < 0: a[i] += mod

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