You are given two positive integers N and K. You have to perform the following operation exactly K times:
- For the current value of N, choose any positive integer D such that D is a [divisor] of N and multiply D with N.  
Formally, N := (N * D) such that D is a divisor of current value of N.

Print the sum of all distinct values of the final N you can receive after performing the above operation exactly K times. Since the answer can be large, print it modulo 10^{9} + 7.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case contains two space-separated integers N and K respectively, the initial number and the number of operations.

------ Output Format ------ 

For each test case, output on a new line the sum of all distinct values of the final N you can receive after performing the given operation exactly K times. Since the answer can be large, print it modulo 10^{9} + 7.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{7}$
$1 ≤ K ≤ 10^{5}$

----- Sample Input 1 ------ 
3
1 5
2 2
10 1
----- Sample Output 1 ------ 
1
30
180
----- explanation 1 ------ 
Test case $1$: $1$ is the only divisor of $1$. So, the value remains unchanged after the operations. Thus, there is only one distinct value after $5$ operations, which is $1$.

Test case $2$: 
- Operation $1$: Initially, $N = 2$ has divisors $1$ and $2$. Thus, after $1$ operation, $N$ can be either $2\cdot 1 = 2$ or $2\cdot 2 = 4$.
- Operation $2$: If $N=2$, the divisors are $1$ and $2$ which can lead to the final values as $2\cdot 1 = 2$ and $2\cdot 2 = 4$. If $N = 4$, the divisors are $1, 2, $ and $4$. Thus, the final values can be $4\cdot 1 = 4, 4\cdot 2 = 8, $ and $4\cdot 4 = 16$ .

The distinct values that can be obtained after applying the operation $2$ times on $N = 2$ are $\{2, 4, 8, 16\}$, and $2 + 4 + 8 + 16 = 30$.

Test case $3$: The numbers $10 = 10 \cdot 1$, $20 = 10 \cdot 2$, $50 = 10 \cdot 5$ and $100 = 10 \cdot 10$ can be obtained after applying the operation $1$ time on $N=10$, and $10 + 20 + 50 + 100 = 180$.

Difficulty: HARD
Tags: Number theory

Mathematics

Starter code:

Solutions:
cons = 1000000007
T = int(input())
for i in range(T):

	def p1(y, z, cons):
		ans = 1
		while z:
			if z % 2 == 1:
				ans = ans * y % cons
			y = y * y % cons
			z //= 2
		return ans

	def p2(x, y):
		if y >= 30:
			return p1(x, p1(2, y, cons - 1) + cons - 1, cons)
		return p1(x, 1 << y, cons)
		return int(' ')

	def calc(a, x, b):
		return (p1(p2(a, b), x, cons) - p1(a, x - 1, cons) + cons) % cons * a % cons * p1(a - 1, cons - 2, cons) % cons
	(a, b) = map(int, input().split())
	Sum = 1
	for j in range(2, a):
		if j * j > a:
			break
		c = 0
		while a % j == 0:
			c += 1
			a //= j
		if c != 0:
			Sum = Sum * calc(j, c, b) % cons
	if a != 1:
		Sum = Sum * calc(a, 1, b) % 1000000007
	print(Sum)


import math
Primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989]
len_p = len(Primes)
T = int(input())
for tc in range(T):
	(N, K) = map(int, input().split(' '))
	N_Kopie = N
	if N == 1:
		print(1)
	else:
		divid = [0 for _ in range(len_p)]
		i = 0
		while N > 1 and i < len_p:
			if N % Primes[i] == 0:
				divid[i] += 1
				N = N // Primes[i]
			else:
				i += 1
		primes_n = []
		primes_factor = []
		for i in range(len_p):
			if divid[i] > 0:
				primes_n.append(Primes[i])
				primes_factor.append(divid[i])
		if N > 1:
			primes_n.append(N)
			primes_factor.append(1)
		total = 0
		end_track = 0
		total = N_Kopie
		for track in range(len(primes_n)):
			subc = pow(2, K, 10 ** 9 + 6)
			subcbis = (primes_factor[track] * subc - primes_factor[track] + 1) % (10 ** 9 + 6)
			reduced_f = pow(primes_n[track], subcbis, 10 ** 9 + 7)
			upper = (reduced_f - 1) % (10 ** 9 + 7)
			lower = pow(primes_n[track] - 1, 10 ** 9 + 5, 10 ** 9 + 7)
			sum_power = upper * lower % (10 ** 9 + 7)
			total *= sum_power
			total = total % (10 ** 9 + 7)
		print(total)


mod = int(10 ** 9 + 7)

def solve(p, a, k):
	first = pow(p, a, mod)
	ratio = p
	terms = (pow(2, k, mod - 1) * a - a + 1) % (mod - 1)
	res = first * (pow(ratio, terms, mod) - 1) % mod
	res *= pow(ratio - 1, mod - 2, mod)
	return res % mod
for _ in range(int(input())):
	ans = 1
	(n, k) = map(int, input().split())
	for i in range(2, n + 1):
		if i * i > n:
			break
		if n % i != 0:
			continue
		ct = 0
		while n % i == 0:
			n //= i
			ct += 1
		ans *= solve(i, ct, k)
		ans %= mod
	if n > 1:
		ans *= solve(n, 1, k)
		ans %= mod
	print(ans)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	mod = int(1000000000.0 + 7)
	ans = 1

	def solve(p, a, k):
		first = pow(p, a, mod)
		ratio = p
		terms = (pow(2, k, mod - 1) * a - a + 1) % (mod - 1)
		res = first * (pow(ratio, terms, mod) - 1) % mod
		res *= pow(ratio - 1, mod - 2, mod)
		return res % mod
	for i in range(2, N + 1):
		if i ** 2 > N:
			break
		if N % i != 0:
			continue
		ct = 0
		while N % i == 0:
			N //= i
			ct += 1
		ans *= solve(i, ct, K)
		ans %= mod
	if N > 1:
		ans *= solve(N, 1, K)
		ans %= mod
	print(ans)


MOD = 10 ** 9 + 7

def solve(p, a, k):
	first = pow(p, a, MOD)
	terms = (pow(2, k, MOD - 1) * a - a + 1) % (MOD - 1)
	res = first * (pow(p, terms, MOD) - 1) % MOD
	res = res * pow(p - 1, MOD - 2, MOD) % MOD
	return res
for t in range(int(input())):
	ans = 1
	(N, K) = map(int, input().split())
	for i in range(2, N + 1):
		if i * i > N:
			break
		if N % i != 0:
			continue
		cnt = 0
		while N % i == 0:
			N //= i
			cnt += 1
		ans = ans * solve(i, cnt, K) % MOD
	if N > 1:
		ans = ans * solve(N, 1, K) % MOD
	print(ans)


from collections import Counter

def U(n, p):
	x = 0
	while n % p == 0:
		n = int(n / p)
		x += 1
	return x

def T(N):
	d = 2
	A = []
	while N > 1:
		while N % d == 0:
			A.append(d)
			N /= d
		d += 1
		if d * d > N:
			if N > 1:
				A.append(N)
			break
	return A
a = int(input())
for i in range(a):
	(N, K) = map(int, input().split())
	n = int(10 ** 9 + 7)
	B = Counter(T(N))
	x = 1
	for p in B.keys():
		y = pow(int(p), int(B[p]), n)
		g = (int(B[p]) * pow(2, K, n - 1) - int(B[p]) + n) % (n - 1)
		z = (pow(int(p), g, n) - 1 + n) * pow(int(p) - 1, n - 2, n) % n
		m = y * z % n
		x *= m
		x %= n
	print(int(x))


md1 = 1000000007
for i in range(int(input())):

	def powr1(l1, q1, md1):
		z1 = 1
		while q1:
			if q1 % 2 == 1:
				z1 = z1 * l1 % md1
			l1 = l1 * l1 % md1
			q1 //= 2
		return z1

	def apop11(a1, l1):
		if l1 >= 30:
			return powr1(a1, powr1(2, l1, md1 - 1) + md1 - 1, md1)
		return powr1(a1, 1 << l1, md1)
		return int(' ')

	def calci1(q1, p1, k1):
		return (powr1(apop11(q1, k1), p1, md1) - powr1(q1, p1 - 1, md1) + md1) % md1 * q1 % md1 * powr1(q1 - 1, md1 - 2, md1) % md1
	(q1, y1) = map(int, input().split())
	apstj1 = 1
	for i in range(2, q1):
		if i * i > q1:
			break
		s1 = 0
		while q1 % i == 0:
			s1 += 1
			q1 //= i
		if s1 != 0:
			apstj1 = apstj1 * calci1(i, s1, y1) % md1
	if q1 != 1:
		apstj1 = apstj1 * calci1(q1, 1, y1) % md1
	print(apstj1)


x = 1000000007

def power(b, n, m):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % m
		b = b * b % m
		n = int(n / 2)
	return s

def apower(a, b):
	if b >= 30:
		return power(a, power(2, b, x - 1) + x - 1, x)
	return power(a, 1 << b, x)

def cal(n, p, k):
	return (power(apower(n, k), p, x) - power(n, p - 1, x) + x) % x * n % x * power(n - 1, x - 2, x) % x
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	i = 2
	while i * i <= n:
		s = 0
		while n % i == 0:
			s += 1
			n = int(n / i)
		if s != 0:
			ans = ans * cal(i, s, k) % x
		i += 1
	if n != 1:
		ans = ans * cal(n, 1, k) % x
	print(ans)


mod = 1000000007

def power(a, n, MOD):
	p = 1
	while n:
		if n % 2 == 1:
			p = p * a % MOD
		a = a * a % MOD
		n //= 2
	return p

def powerT(a, b):
	x = power(2, b, mod - 1)
	if b >= 30:
		return power(a, x + mod - 1, mod)
	return power(a, 1 << b, mod)

def ans(n, p, k):
	x = powerT(n, k)
	y = power(n, p - 1, mod)
	z = power(n - 1, mod - 2, mod)
	result = power(x, p, mod)
	return (result - y + mod) % mod * n % mod * z % mod
for l in range(int(input())):
	(n, k) = map(int, input().split())
	finalAns = 1
	i = 2
	while i * i <= n:
		p = 0
		while n % i == 0:
			p += 1
			n //= i
		if p != 0:
			finalAns = finalAns * ans(i, p, k) % mod
		i += 1
	if n != 1:
		finalAns = finalAns * ans(n, 1, k) % mod
	print(finalAns)


mod = 1000000007

def power(App, Num, MOD):
	P = 1
	while Num:
		if Num % 2 == 1:
			P = P * App % MOD
		App = App * App % MOD
		Num = Num // 2
	return P

def powerT(CA, CB):
	xon = power(2, CB, mod - 1)
	if CB >= 30:
		return power(CA, xon + mod - 1, mod)
	return power(CA, 1 << CB, mod)

def ans(N, p, kil):
	CX = powerT(N, kil)
	CY = power(N, p - 1, mod)
	CZ = power(N - 1, mod - 2, mod)
	result = power(CX, p, mod)
	return (result - CY + mod) % mod * N % mod * CZ % mod

def solve():
	(gn, gk) = list(map(int, input().split()))
	finalanswer = 1
	for i in range(2, gn, 1):
		if i * i > gn:
			break
		p = 0
		while gn % i == 0:
			p += 1
			gn = gn // i
		if p != 0:
			finalanswer = finalanswer * ans(i, p, gk) % mod
	if gn != 1:
		finalanswer = finalanswer * ans(gn, 1, gk) % mod
	print(finalanswer)
testcases = int(input())
while testcases:
	solve()
	testcases -= 1


mod = 1000000007

def func(v1, n, MOD):
	sum = 1
	while n > 0:
		if n % 2 == 1:
			sum = sum * v1 % MOD
		v1 = v1 * v1 % MOD
		n //= 2
	return sum

def func2(a, v1):
	if v1 >= 30:
		return func(a, func(2, v1, mod - 1) + mod - 1, mod)
	return func(a, 1 << v1, mod)
	return int(' ')

def findres(n, p, k):
	return (func(func2(n, k), p, mod) - func(n, p - 1, mod) + mod) % mod * n % mod * func(n - 1, mod - 2, mod) % mod
for tt in range(int(input())):
	res = 1
	(n, k) = [int(i) for i in input().split()]
	i = 2
	while i * i <= n:
		sum = 0
		while n % i == 0:
			sum += 1
			n //= i
		if sum != 0:
			res = res * findres(i, sum, k) % mod
		i += 1
	if n != 1:
		res = res * findres(n, 1, k) % mod
	print(int(res))


MOD = 10 ** 9 + 7

def mod_inverse_fast(a, m):
	g = gcd(a, m)
	if g != 1:
		return -1
	else:
		return power(a, m - 2, m)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def get_prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return factors

def calculate(A, B, C, M):
	res = power(B, C, M - 1)
	ans = power(A, res, M)
	return ans

def mod_inverse(a, m):
	for x in range(1, m):
		if a % m * (x % m) % m == 1:
			return x
	return -1

def mod_subtract(a, b, m):
	return (a % m - b % m + m) % m

def mod_multiply(a, b, m):
	return a % m * (b % m) % m

def mod_divide(a, b, m):
	return a % m * mod_inverse_fast(b, m) % m

def sum_of_series(n, k, value):
	one = calculate(n, 2, k, MOD)
	one_plus = power(one, value, MOD)
	two = mod_subtract(one_plus, 1, MOD)
	three = mod_multiply(n, two, MOD)
	four = mod_divide(three, n - 1, MOD)
	return four

def plain_sum_of_series(n, k):
	one = power(n, k, MOD)
	two = mod_subtract(one, 1, MOD)
	three = mod_multiply(n, two, MOD)
	four = mod_divide(three, n - 1, MOD)
	return four
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	prime_factors = get_prime_factors(n)
	if n == 1:
		print(1)
		continue
	prime_groups = {}
	for prime_factor in prime_factors:
		if prime_factor in prime_groups:
			prime_groups[prime_factor] += 1
		else:
			prime_groups[prime_factor] = 1
	prime_solutions = {}
	for (key, value) in prime_groups.items():
		one = sum_of_series(key, k, value)
		two = plain_sum_of_series(key, value - 1)
		three = one - two
		prime_solutions[key] = three
	current_value = 1
	for (key, value) in prime_solutions.items():
		current_value = mod_multiply(current_value, value, MOD)
	print(current_value)


mod = 1000000007

def power(a, n, MOD):
	p = 1
	while n:
		if n % 2 == 1:
			p = p * a % MOD
		a = a * a % MOD
		n = n // 2
	return p

def powerT(a, b):
	x = power(2, b, mod - 1)
	if b >= 30:
		return power(a, x + mod - 1, mod)
	return power(a, 1 << b, mod)

def ans(n, p, k):
	x = powerT(n, k)
	y = power(n, p - 1, mod)
	z = power(n - 1, mod - 2, mod)
	result = power(x, p, mod)
	return (result - y + mod) % mod * n % mod * z % mod

def solve():
	(n, k) = map(int, input().split())
	finalanswer = 1
	for i in range(2, n, 1):
		if i * i > n:
			break
		p = 0
		while n % i == 0:
			p += 1
			n = n // i
		if p != 0:
			finalanswer = finalanswer * ans(i, p, k) % mod
	if n != 1:
		finalanswer = finalanswer * ans(n, 1, k) % mod
	print(finalanswer)
t = int(input())
while t:
	solve()
	t -= 1


import math as M_T
Mx_Number = 10000002
Spc_F = [0 for i in range(Mx_Number)]

def Siev_Erit():
	Spc_F[1] = 1
	for i in range(2, Mx_Number):
		Spc_F[i] = i
	for i in range(4, Mx_Number, 2):
		Spc_F[i] = 2
	for i in range(3, M_T.ceil(M_T.sqrt(Mx_Number))):
		if Spc_F[i] == i:
			for j in range(i * i, Mx_Number, i):
				if Spc_F[j] == j:
					Spc_F[j] = i

def getFactor(x):
	Ret_N = list()
	while x != 1:
		Ret_N.append(Spc_F[x])
		x = x // Spc_F[x]
	return Ret_N
Siev_Erit()
for i in range(int(input())):
	a = list(map(int, input().strip().split()))
	pfa = getFactor(a[0])
	dpfa = {}
	Temp_1 = a[0]
	for i in pfa:
		while Temp_1 % i == 0:
			Temp_1 //= i
			if i in dpfa:
				dpfa[i] += 1
			else:
				dpfa[i] = 1
	answer = 1
	for i in dpfa:
		a1 = pow(2, a[1], 1000000006)
		answer *= (pow(i, dpfa[i] * a1 + 1, 1000000007) - pow(i, dpfa[i])) * pow(i - 1, 1000000005, 1000000007)
		anser = answer % 1000000007
	print(answer % 1000000007)


mod = 1000000007

def power(a, n, MOD):
	p = 1
	while n:
		if n % 2 == 1:
			p = p * a % MOD
		a = a * a % MOD
		n = n // 2
	return p

def powerT(a, b):
	x = power(2, b, mod - 1)
	if b >= 30:
		return power(a, x + mod - 1, mod)
	c = 1 << b
	return power(a, c, mod)

def ans(n, p, k):
	x = powerT(n, k)
	y = power(n, p - 1, mod)
	z = power(n - 1, mod - 2, mod)
	result = power(x, p, mod)
	return (result - y + mod) % mod * n % mod * z % mod

def solve():
	(n, k) = map(int, input().split())
	finalAnswer = 1
	i = 2
	while i * i <= n:
		p = 0
		while n % i == 0:
			p += 1
			n //= i
		if p != 0:
			finalAnswer = finalAnswer * ans(i, p, k) % mod
		i += 1
	if n != 1:
		finalAnswer = finalAnswer * ans(n, 1, k) % mod
	print(finalAnswer)

def main():
	testcases = int(input())
	for i in range(testcases):
		solve()
main()


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	suy = [int(i) for i in input().split()]
	n = suy[0]
	k = suy[1]

	def poo(a, b, c):
		cnt = 1
		while b:
			if b % 2:
				cnt = cnt * a % c
			a = a * a % c
			b = b // 2
		return cnt
	res = poo(2, k, mod - 1)
	ans = 1
	i = 2
	while i * i <= n:
		tillnow = 0
		while n % i == 0:
			tillnow += 1
			n = n // i
		if tillnow != 0:
			if k >= 30:
				x = poo(i, res + mod - 1, mod)
			else:
				x = poo(i, 1 << k, mod)
			(a, b, c) = (poo(x + mod, tillnow, mod), poo(i, tillnow - 1, mod), poo(i - 1, mod - 2, mod))
			ans = ans * (a - b + mod) % mod * i % mod * c % mod % mod
		i = i + 1
	if n != 1:
		if k >= 30:
			x = poo(n, res + mod - 1, mod)
		else:
			x = poo(n, 1 << k, mod)
		(a, b, c) = (poo(x, 1, mod), poo(n, 0, mod), poo(n - 1, mod - 2, mod))
		ans = ans * (a - b + mod) % mod * n % mod * c % mod
	print(ans % mod)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
import math

def modInverse(b, m):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m):
	a = a % m
	inv = modInverse(b, m)
	if inv == -1:
		return None
	else:
		return inv * a % m
from collections import Counter

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small
mod = 1000000007
for t in range(int(input())):
	(n, k) = mi()
	f = dict(prime_factors(n))
	ans = int(n)
	for i in f:
		if f[i] == 1:
			temp = pow(i, f[i] * pow(2, k, mod - 1) % (mod - 1), mod) - 1
		else:
			temp = pow(i, (f[i] * pow(2, k, mod - 1) - f[i] + 1) % (mod - 1), mod) - 1
		temp %= mod
		curr = modDivide(temp, i - 1, mod)
		ans *= curr
		ans %= mod
	print(ans)


md = 1000000007
for i in range(int(input())):

	def powr(l, q, md):
		z = 1
		while q:
			if q % 2 == 1:
				z = z * l % md
			l = l * l % md
			q //= 2
		return z

	def apop(a, l):
		if l >= 30:
			return powr(a, powr(2, l, md - 1) + md - 1, md)
		return powr(a, 1 << l, md)
		return int(' ')

	def calci(q, p, k):
		return (powr(apop(q, k), p, md) - powr(q, p - 1, md) + md) % md * q % md * powr(q - 1, md - 2, md) % md
	(q, y) = map(int, input().split())
	apstj = 1
	for i in range(2, q):
		if i * i > q:
			break
		s = 0
		while q % i == 0:
			s += 1
			q //= i
		if s != 0:
			apstj = apstj * calci(i, s, y) % md
	if q != 1:
		apstj = apstj * calci(q, 1, y) % md
	print(apstj)


mod = 1000000007

def power(b, n, mo):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % mo
		b = b * b % mo
		n = n // 2
	return s

def Apow(a, b):
	if b >= 30:
		return power(a, power(2, b, mod - 1) + mod - 1, mod)
	return power(a, 1 << b, mod)

def cal(n, p, k):
	return (power(Apow(n, k), p, mod) - power(n, p - 1, mod) + mod) % mod * n % mod * power(n - 1, mod - 2, mod) % mod
for _ in range(int(input())):
	ans = 1
	(n, k) = list(map(int, input().split(' ')))
	i = 2
	while i * i <= n:
		s = 0
		while n % i == 0:
			s += 1
			n = n // i
		if s != 0:
			ans = ans * cal(i, s, k) % mod
		i += 1
	if n != 1:
		ans = ans * cal(n, 1, k) % mod
	print(ans)


def mkpowmod(MOD):

	def pm(x, n):
		if 0 == n:
			return 1
		if 1 == n:
			return x
		ans = pm(x, n // 2)
		ans = ans * ans
		if n % 2 > 0:
			ans *= x
		return ans % MOD
	return pm

def primefact(n):

	def onep(n, p):
		(a, pa) = (0, 1)
		while n % p == 0:
			n //= p
			pa *= p
			a += 1
		return (a, pa, n)
	ret = []
	(a, pa, n) = onep(n, 2)
	if a > 0:
		ret = [*ret, (2, a, pa)]
	(a, pa, n) = onep(n, 3)
	if a > 0:
		ret = [*ret, (3, a, pa)]
	delta = 2
	p = 5
	while p * p <= n:
		(a, pa, n) = onep(n, p)
		if a > 0:
			ret = [*ret, (p, a, pa)]
		p += delta
		delta = 6 - delta
	if n > 1:
		ret = [*ret, (n, 1, n)]
	return ret
Q = 10 ** 9 + 7
pmQ = mkpowmod(Q)
pmQ1 = mkpowmod(Q - 1)
T = int(input())
while T > 0:
	T -= 1
	(N, K) = [int(s) for s in input().split()]
	ret = 1
	if N > 1:
		rK = pmQ1(2, K)
		for (p, a, pa) in primefact(N):
			t = (p * pmQ(pa, rK) + Q - pa) % Q
			if p > 2:
				t = t * pmQ(p - 1, Q - 2) % Q
			ret = ret * t % Q
	print(ret)


m = 1000000007

def power(b, n, m):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % m
		b = b * b % m
		n //= 2
	return s

def calc_power(a, b):
	if b >= 30:
		return power(a, power(2, b, m - 1) + m - 1, m)
	return power(a, 1 << b, m)
	return int(' ')

def distinct(n, p, k):
	return (power(calc_power(n, k), p, m) - power(n, p - 1, m) + m) % m * n % m * power(n - 1, m - 2, m) % m

def solve():
	(n, k) = map(int, input().split())
	i = 2
	ans = 1
	while i * i <= n:
		s = 0
		while n % i == 0:
			s += 1
			n //= i
		if s != 0:
			ans = ans * distinct(i, s, k) % m
		i += 1
	if n != 1:
		ans = ans * distinct(n, 1, k) % m
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def power(a, n, MOD):
	p = 1
	while n:
		if n % 2 == 1:
			p = p * a % MOD
		a = a * a % MOD
		n = n // 2
	return p

def powerT(a, b):
	x = power(2, b, MOD - 1)
	if b >= 30:
		return power(a, x + MOD - 1, MOD)
	return power(a, 1 << b, MOD)

def ans(n, p, k):
	x = powerT(n, k)
	y = power(n, p - 1, MOD)
	z = power(n - 1, MOD - 2, MOD)
	res = power(x, p, MOD)
	return (res - y + MOD) % MOD * n % MOD * z % MOD
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	fanswer = 1
	i = 2
	while i * i <= n:
		p = 0
		while n % i == 0:
			p += 1
			n = n // i
		if p != 0:
			fanswer = fanswer * ans(i, p, k) % MOD
		i += 1
	if n != 1:
		fanswer = fanswer * ans(n, 1, k) % MOD
	print(fanswer)


mod = 1000000007

def power(b, n, mod):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % mod
		b = b * b % mod
		n = n // 2
	return s

def apo(a, b):
	if b >= 30:
		return power(a, power(2, b, mod - 1) + mod - 1, mod)
	return power(a, 1 << b, mod)

def calc(n, p, k):
	return (power(apo(n, k), p, mod) - power(n, p - 1, mod) + mod) % mod * n % mod * power(n - 1, mod - 2, mod) % mod
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	i = 2
	while i * i <= n:
		s = 0
		while n % i == 0:
			s += 1
			n = n // i
		if s != 0:
			ans = ans * calc(i, s, k) % mod
		i += 1
	if n != 1:
		ans = ans * calc(n, 1, k) % mod
	print(ans)


import math

def sieve(limit=10 ** 7):
	isprime = [False] + [True] * limit
	isprime[1] = False
	for i in range(4, limit + 1, 2):
		isprime[i] = False
	i = 3
	while i * i <= limit:
		if isprime[i]:
			for j in range(i * i, limit + 1, 2 * i):
				isprime[j] = False
		i += 2
	return [p for p in range(limit + 1) if isprime[p]]
PRIMES = sieve()

def decomp(N):
	ANS = {}
	if N >= 2:
		for P in PRIMES:
			while N % P == 0:
				ANS[P] = ANS.get(P, 0) + 1
				N //= P
			if N == 1:
				break
			if P > math.sqrt(N):
				ANS[N] = 1
				break
	return ANS

def modpow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		base = base * base % mod
		exp >>= 1
	return result
MOD = 10 ** 9 + 7

def main(N, K):
	prod = N
	for (p, a) in decomp(N).items():
		x = modpow(2, K, MOD - 1)
		x = ((x - 1) * a + 1) % (MOD - 1)
		x = modpow(p, x, MOD)
		x = (x - 1) % MOD
		y = modpow(p - 1, MOD - 2, MOD)
		prod = prod * x * y % MOD
	return prod
T = int(input().strip())
for _ in range(T):
	(N, K) = [int(x) for x in input().strip().split()[:2]]
	print(main(N, K))


var = 7 + 10 ** 9
for _ in range(int(input())):
	(n, k) = map(int, input().split())

	def power(p, q, r):
		count = 1
		while q:
			if q % 2:
				count = count * p % r
			p = p * p % r
			q = q // 2
		return count
	t = power(2, k, var - 1)
	ans = 1
	i = 2
	while i * i <= n:
		total = 0
		while n % i == 0:
			total = total + 1
			n = n // i
		if total != 0:
			if k >= 30:
				x = power(i, t + var - 1, var)
			else:
				x = power(i, 1 << k, var)
			a = power(x + var, total, var)
			b = power(i, total - 1, var)
			c = power(i - 1, var - 2, var)
			ans = ans * (a - b + var) % var * i % var * c % var % var
		i = i + 1
	if n != 1:
		if k >= 30:
			x = power(n, t + var - 1, var)
		else:
			x = power(n, 1 << k, var)
		a = power(x, 1, var)
		b = power(n, 0, var)
		c = power(n - 1, var - 2, var)
		ans = ans * (a - b + var) % var * n % var * c % var
	print(ans % var)


import math
mod = 10 ** 9 + 7
const = 10 ** 7 + 5
allZeros = [0 for i in range(const)]

def helper():
	allZeros[1] = 1
	for i in range(2, const):
		allZeros[i] = i
	for i in range(4, const, 2):
		allZeros[i] = 2
	for i in range(3, math.ceil(math.sqrt(const))):
		if allZeros[i] == i:
			for j in range(i * i, const, i):
				if allZeros[j] == j:
					allZeros[j] = i

def factors(num):
	arr = []
	while num != 1:
		arr.append(allZeros[num])
		num = num // allZeros[num]
	return arr
helper()
for i in range(int(input())):
	arr = [int(x) for x in input().split()]
	arr1 = factors(arr[0])
	ddict = dict()
	temp = arr[0]
	for i in arr1:
		while temp % i == 0:
			temp = temp // i
			if i in ddict:
				ddict[i] += 1
			else:
				ddict[i] = 1
	res = 1
	for i in ddict:
		power = pow(2, arr[1], mod - 1)
		res *= (pow(i, ddict[i] * power + 1, mod) - pow(i, ddict[i])) * pow(i - 1, mod - 2, mod)
		res = res % mod
	print(res % mod)


def power(b, n, MOD):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % MOD
		b = b * b % MOD
		n = n // 2
	return s

def apower(a, b):
	if b >= 30:
		return power(a, power(2, b, 1000000007 - 1) + 1000000007 - 1, 1000000007)
	return power(a, 1 << b, 1000000007)

def calc(n, p, k):
	return (power(apower(n, k), p, 1000000007) - power(n, p - 1, 1000000007) + 1000000007) % 1000000007 * n % 1000000007 * power(n - 1, 1000000007 - 2, 1000000007) % 1000000007
t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	answer = 1
	i = 2
	while i * i <= n:
		s = 0
		while n % i == 0:
			s = s + 1
			n = n // i
		if s != 0:
			answer = answer * calc(i, s, k) % 1000000007
		i = i + 1
	if n != 1:
		answer = answer * calc(n, 1, k) % 1000000007
	print(answer)


mod = 1000000007

def power(b, n, mo):
	s = 1
	while n:
		if n % 2 == 1:
			s = s * b % mo
		b = b * b % mo
		n = n // 2
	return s

def Apower(a, b):
	if b >= 30:
		return power(a, power(2, b, mod - 1) + mod - 1, mod)
	return power(a, 1 << b, mod)

def calc(n, p, k):
	return (power(Apower(n, k), p, mod) - power(n, p - 1, mod) + mod) % mod * n % mod * power(n - 1, mod - 2, mod) % mod

def solve():
	answer = 1
	(n, k) = list(map(int, input().split(' ')))
	i = 2
	while i * i <= n:
		s = 0
		while n % i == 0:
			s += 1
			n = n // i
		if s != 0:
			answer = answer * calc(i, s, k) % mod
		i += 1
	if n != 1:
		answer = answer * calc(n, 1, k) % mod
	print(answer)
for _ in range(int(input())):
	solve()


import math as Mat
MAX_Num = 10000002
spf = [0 for i in range(MAX_Num)]

def sieve_E():
	spf[1] = 1
	for i in range(2, MAX_Num):
		spf[i] = i
	for i in range(4, MAX_Num, 2):
		spf[i] = 2
	for i in range(3, Mat.ceil(Mat.sqrt(MAX_Num))):
		if spf[i] == i:
			for j in range(i * i, MAX_Num, i):
				if spf[j] == j:
					spf[j] = i

def get_Factorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve_E()
for i in range(int(input())):
	a = list(map(int, input().strip().split()))
	pfa = get_Factorization(a[0])
	dpfa = {}
	tempa = a[0]
	for i in pfa:
		while tempa % i == 0:
			tempa //= i
			if i in dpfa:
				dpfa[i] += 1
			else:
				dpfa[i] = 1
	ans = 1
	for i in dpfa:
		a1 = pow(2, a[1], 1000000006)
		ans *= (pow(i, dpfa[i] * a1 + 1, 1000000007) - pow(i, dpfa[i])) * pow(i - 1, 1000000005, 1000000007)
		ans = ans % 1000000007
	print(ans % 1000000007)


mod = 1000000007
for i in range(int(input())):

	def po(l, q, mod):
		s = 1
		while q:
			if q % 2 == 1:
				s = s * l % mod
			l = l * l % mod
			q //= 2
		return s

	def ap(a, l):
		if l >= 30:
			return po(a, po(2, l, mod - 1) + mod - 1, mod)
		return po(a, 1 << l, mod)
		return int(' ')

	def calci(q, p, k):
		return (po(ap(q, k), p, mod) - po(q, p - 1, mod) + mod) % mod * q % mod * po(q - 1, mod - 2, mod) % mod
	(q, k) = map(int, input().split())
	aps = 1
	for i in range(2, q):
		if i * i > q:
			break
		s = 0
		while q % i == 0:
			s += 1
			q //= i
		if s != 0:
			aps = aps * calci(i, s, k) % mod
	if q != 1:
		aps = aps * calci(q, 1, k) % mod
	print(aps)


import math as mt
MAXN = 10000002
spf = [0 for i in range(MAXN)]

def sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, mt.ceil(mt.sqrt(MAXN))):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret
sieve()
for i in range(int(input())):
	a = list(map(int, input().strip().split()))
	pfa = getFactorization(a[0])
	dpfa = {}
	tempa = a[0]
	for i in pfa:
		while tempa % i == 0:
			tempa //= i
			if i in dpfa:
				dpfa[i] += 1
			else:
				dpfa[i] = 1
	ans = 1
	for i in dpfa:
		a1 = pow(2, a[1], 1000000006)
		ans *= (pow(i, dpfa[i] * a1 + 1, 1000000007) - pow(i, dpfa[i])) * pow(i - 1, 1000000005, 1000000007)
		ans = ans % 1000000007
	print(ans % 1000000007)


MOD = 1000000007
for i in range(int(input())):

	def power(b, n, MOD):
		s = 1
		while n:
			if n % 2 == 1:
				s = s * b % MOD
			b = b * b % MOD
			n //= 2
		return s

	def Apower(a, b):
		if b >= 30:
			return power(a, power(2, b, MOD - 1) + MOD - 1, MOD)
		return power(a, 1 << b, MOD)
		return int(' ')

	def calc(n, p, k):
		return (power(Apower(n, k), p, MOD) - power(n, p - 1, MOD) + MOD) % MOD * n % MOD * power(n - 1, MOD - 2, MOD) % MOD
	(n, k) = map(int, input().split())
	answer = 1
	for i in range(2, n):
		if i * i > n:
			break
		s = 0
		while n % i == 0:
			s += 1
			n //= i
		if s != 0:
			answer = answer * calc(i, s, k) % MOD
	if n != 1:
		answer = answer * calc(n, 1, k) % MOD
	print(answer)


MOD = 10 ** 9 + 7
import sys
sys.setrecursionlimit(10000000)
import random
from functools import lru_cache

def primesbelow(N):
	correction = N % 6 > 1
	N = {0: N, 1: N - 1, 2: N + 4, 3: N + 3, 4: N + 2, 5: N + 1}[N % 6]
	sieve = [True] * (N // 3)
	sieve[0] = False
	for i in range(int(N ** 0.5) // 3 + 1):
		if sieve[i]:
			k = 3 * i + 1 | 1
			sieve[k * k // 3::2 * k] = [False] * ((N // 6 - k * k // 6 - 1) // k + 1)
			sieve[(k * k + 4 * k - 2 * k * (i % 2)) // 3::2 * k] = [False] * ((N // 6 - (k * k + 4 * k - 2 * k * (i % 2)) // 6 - 1) // k + 1)
	return [2, 3] + [3 * i + 1 | 1 for i in range(1, N // 3 - correction) if sieve[i]]
smallprimeset = set(primesbelow(100000))
_smallprimeset = 100000

def isprime(n, precision=7):
	if n < 1:
		raise ValueError('Out of bounds, first argument must be > 0')
	elif n <= 3:
		return n >= 2
	elif n % 2 == 0:
		return False
	elif n < _smallprimeset:
		return n in smallprimeset
	d = n - 1
	s = 0
	while d % 2 == 0:
		d //= 2
		s += 1
	for repeat in range(precision):
		a = random.randrange(2, n - 2)
		x = pow(a, d, n)
		if x == 1 or x == n - 1:
			continue
		for r in range(s - 1):
			x = pow(x, 2, n)
			if x == 1:
				return False
			if x == n - 1:
				break
		else:
			return False
	return True

def pollard_brent(n):
	if n % 2 == 0:
		return 2
	if n % 3 == 0:
		return 3
	(y, c, m) = (random.randint(1, n - 1), random.randint(1, n - 1), random.randint(1, n - 1))
	(g, r, q) = (1, 1, 1)
	while g == 1:
		x = y
		for i in range(r):
			y = (pow(y, 2, n) + c) % n
		k = 0
		while k < r and g == 1:
			ys = y
			for i in range(min(m, r - k)):
				y = (pow(y, 2, n) + c) % n
				q = q * abs(x - y) % n
			g = gcd(q, n)
			k += m
		r *= 2
	if g == n:
		while True:
			ys = (pow(ys, 2, n) + c) % n
			g = gcd(abs(x - ys), n)
			if g > 1:
				break
	return g
smallprimes = primesbelow(1000)

def primefactors(n, sort=False):
	factors = []
	for checker in smallprimes:
		while n % checker == 0:
			factors.append(checker)
			n //= checker
		if checker > n:
			break
	if n < 2:
		return factors
	while n > 1:
		if isprime(n):
			factors.append(n)
			break
		factor = pollard_brent(n)
		factors.extend(primefactors(factor))
		n //= factor
	if sort:
		factors.sort()
	return factors

def factorization(n):
	factors = {}
	for p1 in primefactors(n):
		try:
			factors[p1] += 1
		except KeyError:
			factors[p1] = 1
	return factors
totients = {}

def totient(n):
	if n == 0:
		return 1
	try:
		return totients[n]
	except KeyError:
		pass
	tot = 1
	for (p, exp) in factorization(n).items():
		tot *= (p - 1) * p ** (exp - 1)
	totients[n] = tot
	return tot

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

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

@lru_cache(None)
def modInverse(b, m=MOD):
	g = math.gcd(b, m)
	if g != 1:
		return -1
	else:
		return pow(b, m - 2, m)

def modDivide(a, b, m=MOD):
	a = a % m
	inv = modInverse(b, m)
	return inv * a % m
from functools import lru_cache

def gcp_sum(n, power):
	a = pow(n, power + 1, MOD) - 1
	b = n - 1
	res = modDivide(a, b, MOD)
	return res % MOD

def calculate(A, B, C, M):
	res = pow(B, C, M - 1)
	ans = pow(A, res, M)
	return ans

def gcp_sum_big(n, k, power):
	a = pow(calculate(n, 2, k, MOD), power, MOD)
	a = a * n - 1
	b = n - 1
	res = modDivide(a, b, MOD)
	return res % MOD

def solve(n, k):
	factors = factorization(n)
	res = 1
	for (n, power) in factors.items():
		(n, power) = (n % MOD, power % MOD)
		r = gcp_sum_big(n, k, power) - gcp_sum(n, power - 1)
		res = res * r % MOD
	return res
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	print(solve(n, k))