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









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

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

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

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



ans=[0]*(k+1)
p=10**9+7
result=0
for i in range(k):
    num=k-i

    ans[num]=pow(k//num,n,p)
    j=2
    while num*j<=k:
        ans[num]-=ans[num*j]
        j+=1
    result+=((ans[num]*num)%p)    
    
print(result%p)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def solve(N: int, K: int):
    ret = 0
    counts = [0] * (K + 1)
    for i in range(1, K + 1)[::-1]:
        c = K // i
        cnt = pow(c, N, MOD)
        j = 2
        while i * j <= K:
            cnt -= counts[i * j]
            j += 1
        ret += cnt * i
        ret %= MOD
        counts[i] = cnt
    
    print(ret)
    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
"""
dp[i] := gcd(a1,...,an) = i となるものがいくつあるか
"""
dp = [0 for _ in range(k+1)]
subdp = [0 for _ in range(k+1)]
for i in range(1, k+1)[::-1]:
	target = pow(k//i, n, mod)
	for j in range(2*i, k+1, i):
		target -= dp[j]
	dp[i] = target
ans = 0
for i in range(k+1):
	ans = (ans + dp[i]*i) % mod
print(ans)

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

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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N,K = getNM()
ans = 0
rec = [0] * (K + 1)

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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
memo = [-1] * (K + 1)


def rec(x):
    if memo[x] >= 0:
        return memo[x]
    multi = 0
    
    for i in range(x * 2, K + 1, x):
        multi += rec(i)
    memo[x] = pow(K // x, N, mod) - multi
    res = memo[x]
    return res

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

Solution (Python):

MOD = 10**9+7

def pow_mod(x,n):
    if n==0:
        return 1
    elif n%2==0:
        return (pow_mod((x**2)%MOD,n//2))%MOD
    else:
        return (x*pow_mod((x**2)%MOD,n//2))%MOD

N,K = map(int,input().split())
ans = 0
rec = [0]*(K+1)
for X in range(K,0,-1):
    rec[X] = pow_mod(K//X,N)
    for i in range(2,K//X+1):
        rec[X] = (rec[X]-rec[i*X])%MOD
    ans = (ans+X*rec[X])%MOD
print(ans)

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

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7



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


print(functools.reduce(lambda s, x: ((x[0]+1) * x[1] + s)%MOD, enumerate(num), 0))

Solution (Python):
n,k=map(int,input().split())
num=[0]*k
ans=0

def njo(arg,n):
  if n==0:
    return 1
  elif n%2==0:
    return njo((arg**2)%1000000007,n//2)
  else:
    return arg*njo((arg**2)%1000000007,n//2)

for i in range(k):
  test=k-i
  num[test-1]=njo(k//test,n)
  mul=test*2
  while mul<=k:
    num[test-1]-=num[mul-1]
    mul+=test

  ans+=num[test-1]*test
  
while ans<0:
  ans+=1000000007
print(str(ans%1000000007))

Solution (Python):
def modpow(val, n, mod):
    ret = 1
    while n:
        if n & 1:
            ret = (ret * val) % mod
        val = (val * val) % mod
        n = n >> 1
    return ret


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

my_dict = dict()
ret = 0

for i in range(k, 0, -1):
    tmp = modpow(k // i, n, mod)
    cnt = 2
    while True:
        val = i * cnt
        if val > k:
            break
        else:
            cnt += 1
            tmp -= my_dict[val]
    my_dict[i] = tmp
    ret += tmp * i % mod

print(ret % mod)

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

c=0
for i in range(len(D)):
  c+=D[i]*i
print(c%mod)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7


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

N, K = lr()
answer = 0
reset = [0] * (K+1)
for x in range(K, 0, -1):
    
    nums = K // x
    add = pow(nums, N, MOD)
    add -= reset[x]
    answer += add * x
    answer %= MOD
    divs = make_divisors(x)
    for d in divs:
        reset[d] += add

print(answer%MOD)

Solution (Python):
N,K = map(int,input().split())
gcddic = {}
mod_n = (10**9+7)
for i in range(K,0,-1):
    x = pow((K//i),N,mod_n)
    ll=2
    while(ll*i<=K):
        x -= gcddic[ll*(i)]
        ll += 1
    gcddic[i] = x
sumnation = 0
for i,l in gcddic.items():
    sumnation += i*l
print(sumnation%mod_n)

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

    M={}

    mod=pow(10,9)+7
    res=0
    for i in range(K,0,-1):
        syou=K//i
        mc=pow(syou,N,mod)
        if syou>=2:
            for sub_m in range(2,syou+1):
                mc-=M[sub_m*i]
        res+=(i*mc)%mod
        M[i]=mc

    print(res%mod)

if __name__=="__main__":
    main()

Solution (Python):
N,K = list(map(int, input().split()))
mod = int(1e9+7)
A = [0] * (K+1)
ans = 0

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

Solution (Python):
n, k = map(int, input().split())
res = 0
cnt = [0] * (k + 1)
M = int(1e9) + 7

def pow(b, e, m):
    res = 1
    while e:
        if e & 1: res = res * b % m
        e >>= 1
        b = b * b % m
    return res

for i in reversed(range(1, k + 1)):
    t = k // i
    cnt[i] = pow(t, n, M)
    for j in range(i + i, k + 1, i):
        cnt[i] -= cnt[j]

    res = (res + cnt[i] * i) % M

print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())

N,K=LI()

BUF=[0]*(K+1)
for i in reversed(range(1, K+1)):
    pat = POW(K//i, N)
    for j in range(2, K+1):
        if i*j <= K:
            pat -= BUF[i*j]
        else:
            break
    
    BUF[i] = pat

res = 0
for i, j in enumerate(BUF):
    res += (i*j) % DVSR
print(res%DVSR)

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, K = LI()


"""
X = gcd(A_1, A_2,...A_K)
となるようなXを考えると溶ける
X = 3の時その個数は
[K/3]**N
"""

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

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

Solution (Python):
'''
@sksshivam007 - Template 1.0
'''
import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))

INF = float('inf')
mod = 10 ** 9 + 7

n, k = MAP()

a = [0]*(k+1)

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

print(final%mod)

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

Solution (Python):
Mod = 1000000000 + 7

def fastpow(x,y):
    ans = 1

    global Mod
    while y:
        if (y & 1): ans = (ans * x) % Mod
        x = (x * x) % Mod
        y >>= 1
    return ans

def solve(N,K):
    
    
    f = [0]*(K + 1)
    for i in range(K,0,-1):
        f[i] = fastpow(K//i,N)
        for j in range(i + i,K + 1,i):
            f[i] -= f[j]

    global Mod
    ans = 0
    for i in range(1,K + 1):
        ans = (ans + i*f[i]) % Mod
    return ans


if __name__ == "__main__":
    
    N, K = map(int,input().split())
    print(solve(N,K))

Solution (Python):
def sumGCD(N,K,M):
    dp = [None for _ in range(K+1)]
    
    for i in reversed(range(1,K+1)):
        dp[i] = pow(K//i,N,M)
        for j in range(2,K//i+1):
            dp[i] -= dp[i*j]
            dp[i] %= M

    output = 0
    for i in range(1,K+1):
        output += (dp[i]*i)
        output %= M

    return output

def main():
    N,K = map(int,input().split())

    print(sumGCD(N,K,10**9+7))

if __name__ == "__main__":
    main()

Solution (Python):

def solve(N, K):
    mod = 10 ** 9 + 7
    multiples = [[] for _ in range(K + 1)]
    for k in range(1, K + 1):
        for i in range(k, K + 1, k):
            multiples[k].append(i)

    gcdcounts = [0] * (K + 1)  
    gcdsums = [0] * (K + 1)   
    for k in reversed(range(1, K + 1)):
        x = pow(len(multiples[k]), N, mod)
        for l in multiples[k]:
            x -= gcdcounts[l]
        gcdcounts[k] = x % mod
        gcdsums[k] = x * k % mod
    print(sum(gcdsums) % mod)


if __name__ == '__main__':
    N, K = map(int, input().split())
    solve(N, K)

Solution (Python):



MOD = 10 ** 9 + 7

n, k = map(int, input().split())
dic = [0] * (k + 1)

ans = 0
for i in range(k, 0, -1):
  dic[i] = pow(k // i, n, MOD)

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

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

print(ans)

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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = nm()


def solve():
    ans = 0
    tbl = [0] * (K + 1)
    for i in range(K, 0, -1):
        m = K // i
        p = pow(m, N, MOD)

        j = 2
        while j * i <= K:
            p += MOD - tbl[j * i] % MOD
            p %= MOD
            j += 1
        tbl[i] = p

        ans += i * p % MOD
        ans %= MOD
    return ans


print(solve())

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

MOD = 10 ** 9 + 7
N, K = nm()


def solve():
    ans = 0
    tbl = [0] * (K + 1)
    for i in range(K, 0, -1):
        m = K // i
        p = pow(m, N, MOD)

        j = 2
        while j * i <= K:
            p += MOD - tbl[j * i] % MOD
            p %= MOD
            j += 1
        tbl[i] = p

        ans += i * p % MOD
        ans %= MOD
    return ans


print(solve())

Solution (Python):

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

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



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

res = 0
for i, v in enu(d):
    res += i*v
    res %= MOD
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

lst = [0] * (K + 1)

for i in range(K, 0, -1):
    a = K // i
    tmp = pow(a, N, MOD)
    for j in range(i + i, K + 1, i):
        tmp -= lst[j]
    lst[i] = tmp

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

print (ans)

Solution (Python):
N, K = [int(i) for i in input().split()]
MOD = 10**9 + 7

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(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(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))
        )


memo = [-1] * K
def count(k):
    if(memo[k-1] != -1):
        return memo[k-1]
    
    if(k > K//2):
        memo[k-1] = ModInt(1)
        return memo[k-1]
    
    res = ModInt(K//k) ** N
    for i in range(2, K//k + 1):
        res -= count(i * k)

    memo[k-1] = res
    return res

ans = 0
for k in range(K, 0, -1):
    ans += count(k) * k
print(ans)

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

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

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

print(ans)

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

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

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

print(ans)

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

mod = 10**9+7

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


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

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

    for j in range(1, num):
        dp[i] -= dp[(j + 1) * i]
    ans += i * dp[i]
    ans %= mod
print(ans)

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


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


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





N,K = IL()

d = DD(int)

for i in range(1,K+1)[::-1]:
  n = K//i

  d[i] = pow(n,N,MOD) - sum(d[j*i] for j in range(2,n+1))
keys = [k for k in d]

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

P(ans)

Solution (Python):
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    ANS = [0]*(K+1)
    for x in range(K,0,-1):
        ans = pow(K//x,N,Q)
        for i in range(2, K+1):
            if x*i > K:
                break
            ans -= ANS[x*i]
        ANS[x] = ans%Q
    print( sum( [ANS[i]*i%Q for i in range(K+1)])%Q)
        
if __name__ == '__main__':
    main()

Solution (Python):
Q = 10**9+7
def main():
    N, K = map( int, input().split())
    ANS = [0]*(K+1)
    for x in range(K,0,-1):
        ans = pow(K//x,N,Q)
        for i in range(2, K+1):
            if x*i > K:
                break
            ans -= ANS[x*i]
        ANS[x] = ans%Q
    print( sum( [ANS[i]*i%Q for i in range(K+1)])%Q)
        
if __name__ == '__main__':
    main()

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

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

nums = [0] * (K+1)
for i in reversed(range(1, K+1)):
    num = pow(K//i, N, MOD)
    for j in range(2*i, K+1, i):
        num -= nums[j]
    nums[i] = num % MOD

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

print(ans)

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for kk in range(2 * k, K + 1, k):
            n -= n_gcd[kk]
        n_gcd[k] = n % P
        ans += k * n_gcd[k]
        ans %= P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for kk in range(2 * k, K + 1, k):
            n -= n_gcd[kk]
        n_gcd[k] = n % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n -= n_gcd[k * m]
        n_gcd[k] = n % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] -= n_gcd[k * m]
        n_gcd[k] %= P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = dict.fromkeys(range(K + 1), 0)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

    ans = 0
    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(K // k, N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P
        ans = (ans + k * n_gcd[k]) % P

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

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

    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(n_multiple[k], N, mod=P)
        for m in range(2, K // k + 1):
            n_gcd[k] = (n_gcd[k] - n_gcd[k * m]) % P

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
P = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())

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

    n_gcd = [0] * (K + 1)
    for k in reversed(range(1, K + 1)):
        n_gcd[k] = pow(n_multiple[k], N, mod=P)
        m = 2
        kk = k * m
        while kk <= K:
            n_gcd[k] = (n_gcd[k] - n_gcd[kk]) % P
            m += 1
            kk = k * m

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


if __name__ == "__main__":
    main()

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

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

baig=[0]*(10**5+1)
exg=[0]*(10**5+1)

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

for j in range(k,0,-1):
    exg[j]=baig[j]
    for jj in range(2*j,k+1,j):
        exg[j]-=exg[jj]
    exg[j]%=MOD
    ans+=exg[j]*j
    ans%=MOD

print(int(ans))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

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

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD
    print(int(ans))
if __name__ == '__main__':
    main()

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

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

for i in range(K, 0, -1):
    n = pow(K//i, N, MOD)

    for j in range(2*i, K+1, i):
        n -= t[j]
    t[i] = n
    ans = (ans + i * n) % MOD
print(ans)

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

for ki in range(k,0,-1):
    a=k//ki
    ans[ki]=pow(a,n,mod)
    i=2
    while i*ki<=k:
        ans[ki]-=ans[i*ki]
        i+=1
b=0
for ki in range(1,k+1):
    b+=(ans[ki]*ki)%mod
    b%=mod
print(b)

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