Problem:
 Score : 500 points    Problem Statement Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).  There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.  Since this sum can be enormous, print the value modulo (10^9+7) .  Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N .      Constraints  2 \leq N \leq 10^5  1 \leq K \leq 10^5  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K       Output Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7) .        Sample Input 1 3 2      Sample Output 1 9  \gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)  +\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)  =1+1+1+1+1+1+1+2=9  Thus, the answer is 9 .       Sample Input 2 3 200      Sample Output 2 10813692       Sample Input 3 100000 100000      Sample Output 3 742202979  Be sure to print the sum modulo (10^9+7) .

Solution (Python):
N, K = [int(_) for _ in input().split()]
mod = 10**9 + 7
A = [0] * (K + 1)
for i in range(K, 0, -1):
    A[i] = pow(K // i, N, mod)
    for j in range(2, K // i + 1):
        A[i] -= A[i * j]
        A[i] %= mod
print(sum(i * a for i, a in enumerate(A)) % mod)

Solution (Python):
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(self.power_func(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(self.power_func(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

    def power_func(self,a,n,p):
        bi=str(format(n,"b"))
        res=1
        for i in range(len(bi)):
            res=(res*res) %p
            if bi[i]=="1":
                res=(res*a) %p
        return res



MOD = 10**9 + 7

N,K=[int(hoge) for hoge in input().split()]
Kazus = [0]*(K+1)
for x in range(K,0,-1):
    Dmax = K//x
    MoDmax = ModInt(Dmax)
    kazu = MoDmax ** N
    for d in range(Dmax,1,-1):
        kazu -= Kazus[d*x]
    Kazus[x] = kazu

print(sum([x*k for x,k in enumerate(Kazus) ]))

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

Solution (Python):



import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf



import math

import bisect

class Solver:

    def __init__(self, n, k):
        self.n = n
        self.k = k
        
        
        self.ans_list = [0] * (k + 1) 
        
        
        self.m = 10 ** 9 + 7

    def gcd_count(self, i):
        times = k // i
        cases = pow(times, n, self.m)
        j = i * 2
        while not (j > k):
            cases -= self.ans_list[j]
            j += i
        
        
        self.ans_list[i] = cases % self.m

    def run(self):
        for i in range(k, 0, -1):
            
            
            self.gcd_count(i)
        ans = 0
        for i, a in enumerate(self.ans_list):
            ans += i * a
        
        
        return ans % self.m



if __name__ == '__main__':
    n, k = list(map(int, input().split()))
    ans = Solver(n, k).run()
    
    print(ans)

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

L = [0]*(k+1)

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

Solution (Python):
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache

sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

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


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

'''
1以上K以下の整数からなる長さNの数列{A_1,...A_N}を考える。
K^N個考えられる数列のgcd(A_1,...A_N)の和を求め、10^9+7で割った余りを出力せよ。

term:
2<=N<=10**5
1<=K<=10**5
input:
3 2
output:
    9
'''

'''
K^N個の数列すべてに対してgcdを計算しているとO((K^N)*(N+logK))になり間に合わない。
そこで、問題を
「1<=X<=Kに対してgcd(A_1,...A_N)=Xとなる数列A_iがいくつあるか」
という問題に読み替える。
Xが最大公約数であるためには{A_1,...A_N}がすべてXの倍数でなければならない。
K以下でXの倍数である数の個数はK//Xで求められる。
これらによって構成される数列は(K//X)^N種類ある。
しかしgcdがXの倍数であるものも含まれてしまうのでそれを包除原理で除く。
ex)
    K=4,N=3のとき(4,4,4)はすべて2の倍数だがgcdは4。
    したがって{(4//2)^3-(4//(2*2))^3}%modとする。
'''

Solution (Python):
import sys
MOD = 10**9+7
def main():
    input = sys.stdin.readline
    N,K=map(int, input().split())
    ans=Mint()
    cnt=[Mint() for _ in range(K+1)]
    for g in range(K,0,-1):
        cnt[g]+=pow(K//g,N,MOD)
        for h in range(g+g,K+1,g):
            cnt[g]-=cnt[h]
        ans+=g*cnt[g]
    print(ans)

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)






















MOD = 10**9+7
import math
N,K = map(int,input().split())
ans = [0]*K
for i in range(K):
    p = K-i
    a = pow(math.floor(K/p),N,MOD)
    x = 1
    while p*(x+1) <= K:
        a -= ans[p*(x+1)-1]
        x = x+1
    ans[p-1] = a%MOD
s = 0
for i in range(K):
    s += (i+1)*ans[i]
    s = s%MOD
print(s)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)






















MOD = 10**9+7
import math
N,K = map(int,input().split())
ans = [0]*K
for i in range(K):
    p = K-i
    a = pow(math.floor(K/p),N,MOD)
    x = 1
    while p*(x+1) <= K:
        a -= ans[p*(x+1)-1]
        x = x+1
    ans[p-1] = a%MOD
s = 0
for i in range(K):
    s += (i+1)*ans[i]
    s = s%MOD
print(s)

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)



class Prime():
    def __init__(self, n):
        self.M = m = int(math.sqrt(n)) + 10
        self.A = a = [True] * m
        a[0] = a[1] = False
        self.T = t = [2]
        for j in range(4, m, 2):
            a[j] = False
        for i in range(3, m, 2):
            if not a[i]:
                continue
            t.append(i)
            for j in range(i*i,m,i):
                a[j] = False
        self.ds_memo = {}
        self.ds_memo[1] = set([1])

    def is_prime(self, n):
        return self.A[n]

    def division(self, n):
        d = collections.defaultdict(int)
        for c in self.T:
            while n % c == 0:
                d[c] += 1
                n //= c
            if n < 2:
                break
        if n > 1:
            d[n] += 1
        return d.items()

    
    def divisions(self, n):
        if n in self.ds_memo:
            return self.ds_memo[n]

        for c in self.T:
            if n % c == 0:
                rs = set([c])
                for cc in self.divisions(n // c):
                    rs.add(cc)
                    rs.add(cc * c)
                self.ds_memo[n] = rs
                return rs

        rs = set([1, n])
        self.ds_memo[n] = rs
        return rs

def main():
    n,k = LI()
    pr = Prime(10**5)
    c = collections.defaultdict(int)
    for i in range(k, 0, -1):
        t = k // i
        p = (pow(t, n, mod) + c[i]) % mod
        ds = pr.divisions(i)
        for kk in ds:
            if kk == i:
                continue
            c[kk] -= p
        c[i] = p

    r = sum(k*v%mod for k,v in c.items()) % mod

    return r

print(main())

Solution (Python):
import sys
import os

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

def main():
    

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

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

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

    print(out%mod)

if __name__ == '__main__':
    main()

Solution (Python):
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))

Solution (Python):
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)
    
    s = 2
    while x * s <= k:
        a -= dict_x[x * s]
        s += 1
    dict_x[x] = a
    answer = (answer + a * x) % mod

print(answer)

Solution (Python):
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 )

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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,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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

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

out = 0
mod = 10**9+7

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

Solution (Python):
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)

Solution (Python):
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


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]


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

Solution (Python):

import sys

MOD = 1000000007  


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



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

if __name__ == '__main__':
    main()

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



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)

Solution (Python):
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)

Solution (Python):
n,k = map(int,input().split())
mod = 10**9+7
gcd = [0]*(k+1)
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)

Solution (Python):
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)

Solution (Python):

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


if __name__ == "__main__":
    main()

Solution (Python):

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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

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

out = 0
mod = 10**9+7

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

Solution (Python):
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)

Solution (Python):
def POW(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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
import math
from collections import defaultdict

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

for i in range(K,0,-1):
    m = K//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)

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

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)

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

Solution (Python):
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(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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)

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

def modpow(a, b): 
    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 
    L = K // k
    C[k] = modpow(L, N) 
    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)