AtCoder Beginner Contest 162 - Sum of gcd of Tuples (Hard)

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-----
3 2

-----Sample Output-----
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.

Difficulty: MEDIUM

Starter code:

Solutions:
(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)


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


mod = 10 ** 9 + 7
(n, k) = list(map(int, input().split()))
c = {i: 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):
		c[i] -= c[j]
_sum = 0
for x in range(1, k + 1):
	_sum += c[x] * x % mod
print(_sum % mod)


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


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


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


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


mod = pow(10, 9) + 7

def main():
	(N, K) = list(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)

def __starting_point():
	main()
__starting_point()


(n, k) = list(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)


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


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


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


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
cnt = [0] * (K + 1)
answer = 0
for i in range(K, 0, -1):
	tmp = pow(K // i, N, mod) - sum(cnt[::i])
	cnt[i] = tmp
	answer = (answer + tmp * i) % mod
print(answer)


(N, K) = map(int, input().split())
MOD = 10 ** 9 + 7
ans = 0
X = [0] * K
for k in range(1, K + 1):
	k = K + 1 - k
	x = K // k
	if x > 1:
		_ = pow(x, N, MOD)
		for i in range(x - 1):
			_ -= X[k * (i + 2) - 1]
		X[k - 1] = _
		ans += k * _
	else:
		X[k - 1] = pow(x, N, MOD)
		ans += k * X[k - 1]
print(ans % MOD)


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


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


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) = list(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)


import sys
import os

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

def main():
	(N, K) = list(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)

def __starting_point():
	main()
__starting_point()


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


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


(n, k) = map(int, input().split())
MOD = 10 ** 9 + 7
cnt = [0] * (k + 1)
for gcd in range(1, k + 1):
	cnt[gcd] = pow(k // gcd, n, MOD)
for gcd in range(k, 0, -1):
	for i in range(2, k // gcd + 1):
		cnt[gcd] -= cnt[gcd * i]
ans = sum([num * c for (num, c) in enumerate(cnt)]) % MOD
print(ans)


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


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


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


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


(n, k) = map(int, input().split())
m = 10 ** 9 + 7
t = pow(k, n, m)
p = [0, 0]
for i in range(2, k + 1):
	p.append(pow(k // i, n, m))
for i in range(k, 1, -1):
	if 2 * i <= k:
		for j in range(2 * i, k + 1, i):
			p[i] -= p[j]
	t += (i - 1) * p[i]
	t %= m
print(t)


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


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
ans = 0
X_gcd = [0] * (K + 1)
for X in reversed(range(1, K + 1)):
	X_gcd[X] = pow(K // X, N, mod)
	for nX in range(2 * X, K + 1, X):
		X_gcd[X] -= X_gcd[nX]
	ans = (ans + X % mod * (X_gcd[X] % mod)) % mod
print(ans % mod)


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


(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
s = [1] * (k + 1)
for d in range(1, k // 2 + 1)[::-1]:
	a = pow(k // d, n, mod)
	for i in range(2 * d, k + 1, d):
		a -= s[i]
	s[d] = a % mod
ans = 0
for (i, s_i) in enumerate(s):
	ans += i * s_i
	ans %= mod
print(ans)


mod = 10 ** 9 + 7
(n, k) = list(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)


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


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


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


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


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


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) = list(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)


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


from functools import reduce
MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
cnt = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
	temp = cnt[2 * k::k]
	cnt[k] = pow(K // k, N, MOD) - (reduce(lambda x, y: (x + y) % MOD, temp) if temp else 0)
	ans += cnt[k] * k % MOD
	ans %= MOD
print(ans)


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


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


(N, K) = [int(x) for x in input().split()]
count = [0] * (K + 1)
ans = 0
mod = 1000000007
for i in range(K, 0, -1):
	kosuu = pow(K // i, N, mod)
	if K // i >= 2:
		for j in range(K // i, 1, -1):
			kosuu -= count[j * i]
	ans += i * kosuu
	count[i] = kosuu
print(ans % mod)


Big = 10 ** 9 + 7
_ = list(map(int, input().split(' ')))
N = _[0]
K = _[1]
gcd_list = [0 for _ in range(K)]
for i in range(K):
	s = K - i - 1
	gcd_list[s] = (pow(K // (K - i), N, Big) - sum(gcd_list[2 * s + 1::s + 1]) % Big) % Big
answer = [(x + 1) * gcd_list[x] % Big for x in range(K)]
print(sum(answer) % Big)


import sys
sys.setrecursionlimit(10 ** 8)
ni = lambda : int(sys.stdin.readline())
nm = lambda : list(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())


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


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


(n, k) = map(int, input().split())
mod = MOD = 10 ** 9 + 7
G = [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, k // i + 1):
		G[i] -= G[j * i]
print(sum([i * f for (i, f) in enumerate(G)]) % mod)


(N, K) = map(int, input().split())
ans = 0
MOD = 10 ** 9 + 7
cnt = [0] * (K + 1)
for x in reversed(range(1, K + 1)):
	t = K // x
	cnt_tmp = pow(t, N, MOD)
	t = 1
	while (t + 1) * x <= K:
		t += 1
		cnt_tmp -= cnt[x * t]
	g = x * cnt_tmp % MOD
	cnt[x] += cnt_tmp
	ans += g
	ans %= MOD
print(ans)


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


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


from collections import defaultdict
(N, K) = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
dd = defaultdict(int)
ans = 0
for i in range(K, 0, -1):
	dd[i] = pow(K // i, N, mod)
	for temp in range(i * 2, K + 1, i):
		dd[i] -= dd[temp]
	ans += dd[i] * i
	ans %= mod
print(ans)


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)


(N, K) = list(map(int, input().split()))
mod = 10 ** 9 + 7
fact_count = [0 for _ in range(K + 1)]
for k in range(1, K + 1):
	fact_count[k] = K // k
ans = 0
count = [0 for _ in range(K + 1)]
for k in range(K, 0, -1):
	c = pow(fact_count[k], N, mod)
	j = 2 * k
	l = 2
	while j <= K:
		c -= count[j]
		l += 1
		j = k * l
	count[k] = c
	c = c * k % mod
	ans += c
	ans %= mod
print(ans)


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


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

def main():
	(N, K) = list(map(int, input().split()))
	ans = 0
	n_gcd = [0] * (K + 1)
	for k in reversed(list(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)

def __starting_point():
	main()
__starting_point()


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


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


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)

def __starting_point():
	main()
__starting_point()


(N, K) = list(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)


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
G = [1] * (K + 1)
ans = 0
for k in range(K, 0, -1):
	x = K // k
	t = int(pow(x, N, mod))
	for j in range(x - 1):
		t -= G[(j + 2) * k]
	G[k] = t
	ans += t * k
	ans %= mod
print(ans)


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)


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


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)


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


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)


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


(N, K) = list(map(int, input().split()))
mod = int(1000000000.0 + 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)


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


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


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


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

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

def __starting_point():
	main()
__starting_point()


(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 ** 0.5) + 1):
		if i % j == 0:
			d[j] += t
			if j != i // j:
				d[i // j] += t
print(ans)


MOD = 10 ** 9 + 7
(n, k) = map(int, input().strip().split())
d = [0] * (k + 1)
d[0] = None
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 % MOD
	ans %= MOD
print(ans)


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


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


(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(1000000000.0 + 7))
	s[i] %= 1000000000.0 + 7
	for j in range(i * 2, k + 1, i):
		s[i] += 1000000000.0 + 7
		s[i] -= s[j]
		s[i] %= 1000000000.0 + 7
for i in range(1, k + 1):
	ans += i * s[i]
	ans %= 1000000000.0 + 7
ans %= 1000000000.0 + 7
print(int(ans))


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


(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(i + i, k + 1, i):
		dp[i] -= dp[j]
ans = sum([i * dp[i] for i in range(k + 1)])
ans %= MOD
print(ans)


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


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


Q = 10 ** 9 + 7

def main():
	(N, K) = list(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)

def __starting_point():
	main()
__starting_point()


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


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


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


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


(N, K) = map(int, input().split())
H = [0] * (K + 1)
m = pow(10, 9) + 7
ans = 0
i = K
while i >= 1:
	H[i] = pow(K // i, N, m)
	j = 2
	while j * i <= K:
		H[i] -= H[j * i]
		j += 1
	ans += H[i] * i
	i -= 1
print(ans % m)


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


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


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

def __starting_point():
	(N, K) = list(map(int, input().split()))
	solve(N, K)
__starting_point()


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


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache

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

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def TUPLE():
	return tuple(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
(N, K) = MAP()
gcd_cnt = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
	cnt = pow(K // i, N, mod)
	for j in range(2, K // i + 1):
		cnt -= gcd_cnt[j * i]
		cnt %= mod
	gcd_cnt[i] = cnt
	ans += i * cnt
	ans %= mod
print(ans)


def sumGCD(N, K, M):
	dp = [None for _ in range(K + 1)]
	for i in reversed(list(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) = list(map(int, input().split()))
	print(sumGCD(N, K, 10 ** 9 + 7))

def __starting_point():
	main()
__starting_point()


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


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)


MOD = 10 ** 9 + 7
(n, k) = map(int, input().split())
cnt = [0] * (k + 1)
for i in range(1, k + 1):
	cnt[i] = pow(k // i, n, MOD)
dp = [0] * (k + 1)
for i in reversed(range(1, k + 1)):
	if not cnt[i]:
		continue
	tmp = cnt[i]
	for j in range(2, k + 1):
		if k < i * j:
			break
		tmp -= dp[i * j]
		tmp %= MOD
	dp[i] = tmp
ans = 0
for i in range(1, k + 1):
	ans += i * dp[i]
	ans %= MOD
print(ans)


(N, K) = map(int, input().split())
DIV = 10 ** 9 + 7
num = [0] * (K + 1)
ans = 0
for x in range(K, 0, -1):
	num[x] = pow(K // x, N, DIV)
	for temp in range(x * 2, K + 1, x):
		num[x] -= num[temp]
	ans += num[x] * x
	ans %= DIV
print(ans)


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


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


M = 10 ** 9 + 7
(n, k) = map(int, input().split())
d = [0] * -~k
a = 0
for i in range(k, 0, -1):
	t = c = 0
	for j in range(i, k + 1, i):
		c += 1
		t += d[j]
	d[i] = pow(c, n, M) - t
	a = (a + i * d[i]) % M
print(a)


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

def f(n, k):
	res = 0
	lst = [0] * (k + 1)
	for i in range(k, 0, -1):
		lst[i] = pow(k // i, n, m) - sum((lst[i * j] for j in range(2, k // i + 1))) % m
		res += i * lst[i]
		res %= m
	return res
print(f(n, k))


import math
(N, K) = map(int, input().split())
a = [0] * (K + 1)
co = 0
mod = 10 ** 9 + 7
for i in range(K, 0, -1):
	b = K // i
	t = 2 * i
	m = 0
	while t <= K:
		m = m + a[t]
		t += i
	c = pow(b, N, mod)
	a[i] = c - m
	co += a[i] * i % mod
print(co % mod)


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


(n, k) = map(int, input().split())
mod = int(1000000000.0 + 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)


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


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


def main():
	(N, K) = map(int, input().split())
	mod = 10 ** 9 + 7
	r = 0
	D = [0] * (K + 1)
	for i in reversed(range(1, K + 1)):
		D[i] = pow(K // i, N, mod) - sum(D[::i])
	return sum((i * j for (i, j) in enumerate(D))) % mod
print(main())


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


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


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


def main():
	import sys

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

def __starting_point():
	main()
__starting_point()


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


(N, K) = map(int, input().split())
dp = [0] * (K + 1)
MOD = 10 ** 9 + 7
ans = 0
for X in range(K, 0, -1):
	m = pow(K // X, N, MOD)
	x = 2 * X
	while x <= K:
		m -= dp[x]
		m %= MOD
		x += X
	ans += X * m
	ans %= MOD
	dp[X] = m
print(ans)


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


(N, K) = list(map(int, input().split()))
MOD = 1000000007
gcd_cnt = [0] * (K + 1)
for g in range(K, 0, -1):
	gcd_cnt[g] = pow(K // g, N, MOD)
	for g_mul in range(2, K // g + 1):
		gcd_cnt[g] -= gcd_cnt[g * g_mul]
ans = 0
for (g, cnt) in enumerate(gcd_cnt):
	ans += g * cnt % MOD
	ans %= MOD
print(ans)


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


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


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

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


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


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


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


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
ans = [0] * (K + 1)
result = 0
for i in range(K, 0, -1):
	c = K // i
	ans[i] += pow(c, N, mod)
	for j in range(i, K + 1, i):
		if i != j:
			ans[i] -= ans[j]
	result += i * ans[i] % mod
print(result % mod)


(N, K) = list(map(int, input().split()))
l = [0] * (K + 1)
ans = 0
mod = 10 ** 9 + 7
for x in range(K, 0, -1):
	l[x] = pow(K // x, N, mod)
	for y in range(2 * x, K + 1, x):
		l[x] -= l[y]
		l[x] = pow(l[x], 1, mod)
	ans += l[x] * x
	ans = pow(ans, 1, mod)
print(ans)


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


from math import gcd
(N, K) = list(map(int, input().split()))
mod = 10 ** 9 + 7
A = [0] * K
for i in range(K, 0, -1):
	a = K // i
	b = pow(a, N, mod)
	A[i - 1] = b
for i in range(K, 0, -1):
	for j in range(K // i - 1):
		c = i * (j + 2)
		A[i - 1] -= A[c - 1]
		A[i - 1] %= mod
s = 0
for i in range(K):
	s += A[i] * (i + 1)
	s %= mod
print(s)


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)


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

def getnum(m):
	ret = pow(k // m, n, mod)
	mul = 2
	while m * mul <= k:
		ret -= count[m * mul]
		mul += 1
	return ret % mod
ans = 0
for i in range(1, k + 1)[::-1]:
	g = getnum(i)
	count[i] = g
	ans += g * i
	ans %= mod
print(ans)


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


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


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


(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
result = 0
memo = [0 for _ in range(k + 1)]
for i in range(k, 0, -1):
	y = k // i
	z = pow(y, n, mod)
	j = 2
	while j * i <= k:
		z -= memo[j * i]
		z %= mod
		j += 1
	memo[i] = z
	result = (result + z * i) % mod
print(result)


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


(N, K) = map(int, input().split())
MOD = int(1000000000.0) + 7
dp = [0] * (K + 1)
for ii in range(K):
	i = K - ii
	dp[i] += pow(K // i, N, MOD)
	j = 2 * i
	while j <= K:
		dp[i] = (dp[i] - dp[j] + MOD) % MOD
		j += i
ans = 0
for i in range(1, K + 1):
	ans += dp[i] * i
	ans %= MOD
print(ans)


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


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


import numpy as np
MOD = 10 ** 9 + 7
(N, K) = list(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)


(N, K) = map(int, input().split())
P = int(1000000000.0 + 7)
cnt = [0] * (K + 1)
ans = 0
for i in range(K, 0, -1):
	c = pow(K // i, N, P) - sum(cnt[::i])
	cnt[i] = c
	ans = (ans + i * c) % P
print(ans % P)


(N, K) = map(int, input().split())
p = 10 ** 9 + 7
S = 0
memo = []
for i in reversed(range(1, K + 1)):
	rep = K // i
	num = pow(rep, N, p)
	sub = 0
	if rep > 1:
		for j in range(rep - 1):
			sub += memo[-i - j * i][1]
	num -= sub
	S += i * num
	S = S % p
	memo += [(i, num)]
print(S)


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


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
gcd = {}
s = 0
for x in range(K, 0, -1):
	i = K // x
	tmp = pow(i, N, mod)
	if i > 1:
		for j in range(2, i + 1):
			tmp -= gcd[j * x]
	gcd[x] = tmp
	s += tmp * x % mod
	s %= mod
print(s)


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


import math
from collections import defaultdict
(N, K) = list(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)


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

def main():
	b = N
	blis = []
	c = 0
	while b > 0:
		if b & 1 == 1:
			blis.append(c)
		c += 1
		b >>= 1

	def modpow(a, blis=blis, c=c):
		if a == 1:
			return 1
		else:
			res = 1
			li = []
			for _ in range(c):
				li.append(a % mod)
				a = a * a % mod
			for item in blis:
				res = res * li[item] % mod
			return res
	fact_count = [0 for _ in range(K + 1)]
	for k in range(1, K + 1):
		fact_count[k] = K // k
	ans = 0
	count = [0 for _ in range(K + 1)]
	for k in range(K, 0, -1):
		x = 1 * fact_count[k]
		cc = modpow(x)
		j = 2 * k
		l = 2
		while j <= K:
			cc -= count[j]
			l += 1
			j = k * l
		count[k] = cc
		cc = cc * k % mod
		ans += cc
		ans %= mod
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
mod = 10 ** 9 + 7
gcd_l = [0] * K
for i in range(K, 0, -1):
	n = pow(K // i, N, mod)
	for x in range(i, K + 1, i):
		n -= gcd_l[K - x]
	gcd_l[K - i] = n % mod
res = 0
for i in range(K):
	res += gcd_l[i] * (K - i) % mod
print(res % mod)


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


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


(N, K) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
ans = 0
gcds = [0] * (K + 1)
for i in reversed(list(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)


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


(N, K) = map(int, input().split(' '))
mod = 10 ** 9 + 7
dp = [0 if i == 0 else pow(K // i, N, mod) for i in range(K + 1)]
for i in range(K, 0, -1):
	for j in range(2, K // i + 1):
		dp[i] -= dp[i * j]
ans = 0
for i in [n * i % mod for (n, i) in enumerate(dp)]:
	ans += i
	ans %= mod
print(ans)


(n, k) = map(int, input().split())
X = [0] * (k + 1)
mod = 10 ** 9 + 7
for x in range(k, 0, -1):
	X[x] = pow(k // x, n, mod)
	for x_multi in range(x * 2, k + 1, x):
		X[x] -= X[x_multi]
print(sum((i * x for (i, x) in enumerate(X))) % mod)


(n, k) = list(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)


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)


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


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


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

def calc(x):
	M = K // x
	c = pow(M, N, MOD)
	for i in range(x + x, K + 1, x):
		c -= cnt[i]
	cnt[x] = c
	return c * x
ans = 0
for x in range(1, K + 1)[::-1]:
	ans = (ans + calc(x)) % MOD
print(ans)


(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):
	nonlocal 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)


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


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)


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


Mod = 1000000000 + 7

def fastpow(x, y):
	ans = 1
	nonlocal 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]
	nonlocal Mod
	ans = 0
	for i in range(1, K + 1):
		ans = (ans + i * f[i]) % Mod
	return ans

def __starting_point():
	(N, K) = list(map(int, input().split()))
	print(solve(N, K))
__starting_point()


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


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


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


def resolve():
	MOD = 10 ** 9 + 7
	(N, K) = map(int, input().split())
	cnt = [0] * (K + 1)
	for g in range(K, 0, -1):
		cnt[g] = pow(K // g, N, MOD)
		gg = g * 2
		while gg <= K:
			cnt[g] -= cnt[gg]
			gg += g
	ans = 0
	for g in range(1, K + 1):
		ans += cnt[g] * g
		ans %= MOD
	print(ans)

def __starting_point():
	resolve()
__starting_point()


(N, K) = map(int, input().split())
MOD = 10 ** 9 + 7
ans = 0
ctr = [0] * (K + 1)
for x in reversed(range(1, K + 1)):
	ctr[x] = pow(K // x, N, MOD)
	for y in range(2 * x, K + 1, x):
		ctr[x] -= ctr[y]
ans = 0
for n in range(1, K + 1):
	ans += n * ctr[n]
	ans %= MOD
print(ans)


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


(n, k) = (int(x) for x in input().split())
c = {}
t = 0
MOD = 1000000007
for x in range(k, 0, -1):
	q = k // x
	c[x] = pow(q, n, MOD) - sum((c[x * y] for y in range(2, q + 1)))
	t += c[x] * x
	t = t % 1000000007
print(t)


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)


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


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


def main():
	import sys
	input = sys.stdin.readline
	(n, k) = list(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))

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
p = int(1000000000.0 + 7)
res = 0
d = [0] * K
for i in range(K, 0, -1):
	n = pow(K // i, N, p)
	for j in range(2 * i, K + 1, i):
		n -= d[j - 1]
	d[i - 1] = n
	res += n * i
	res %= p
print(res)


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


(N, K) = list(map(int, input().split()))
mod = int(1000000000.0 + 7)
d = dict()
ans = 0
for X in range(K, 0, -1):
	res = pow(K // X, N, mod)
	for k in range(2 * X, K + 1, X):
		res -= d[k]
	d[X] = res % mod
	ans += res * X % mod
print(ans % mod)


(n, k) = list(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)


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


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


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


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


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)


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


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


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)


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


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
INF = 10 ** 9 + 7
l = [0] * k
ans = 0
for i in range(k - 1, -1, -1):
	x = i + 1
	temp = pow(k // x, n, INF)
	for j in range(2, k // x + 1):
		temp = (temp - l[j * x - 1]) % INF
	l[i] = temp
	ans = (ans + x * temp) % INF
print(ans)


MOD = 10 ** 9 + 7
(N, K) = map(int, input().split())
A = [0] * (K + 1)
for d in range(1, K + 1):
	A[d] = pow(K // d, N, MOD)
for d in range(K, 0, -1):
	for i in range(2, K // d + 1):
		A[d] -= A[d * i]
answer = sum((d * x for (d, x) in enumerate(A)))
print(answer % MOD)


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


(n, k) = map(int, input().split())
mod = 10 ** 9 + 7
al = [0] * (k + 1)
for x in range(1, k + 1):
	al[x] = pow(k // x, n, mod)
for x in range(k, 0, -1):
	for b in range(2, k // x + 1):
		al[x] -= al[x * b]
res = 0
for i in range(k + 1):
	res += i * al[i]
	res %= mod
print(res)