Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 
Zombies zombies everywhere!! 
In a parallel world of zombies, there are N zombies. There are infinite number of unused cars, each of same model only differentiated by the their colors. The cars are of K colors.

A zombie parent can give birth to any number of zombie-children (possibly zero), i.e. each zombie will have its parent except the head zombie which was born in the winters by combination of ice and fire.

Now, zombies are having great difficulties to commute to their offices without cars, so they decided to use the cars available. Every zombie will need only one car. Head zombie called a meeting regarding this, in which he will allow each zombie to select a car for him.

Out of all the cars, the head zombie chose one of cars for him. Now, he called his children to choose the cars for them. After that they called their children and so on till each of the zombie had a car. Head zombie knew that it won't be a good idea to allow children to have cars of same color as that of parent, as they might mistakenly use that. So, he enforced this rule during the selection of cars.

Professor James Moriarty is a criminal mastermind and has trapped Watson again in the zombie world. Sherlock somehow manages to go there and met the head zombie. Head zombie told Sherlock that they will let Watson free if and only if Sherlock manages to tell him the maximum number of ways in which the cars can be selected by N Zombies among all possible hierarchies. A hierarchy represents parent-child relationships among the N zombies. Since the answer may be large, output the answer modulo 10^{9} + 7. Sherlock can not compute big numbers, so he confides you to solve this for him.

------ Input ------ 

The first line consists of a single integer T, the number of test-cases.

Each test case consists of two space-separated integers N and K, denoting number of zombies and the possible number of colors of the cars respectively.

------ Output ------ 

For each test-case, output a single line denoting the answer of the problem.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{9}$
$1 ≤ K ≤ 10^{9}$

------ Subtasks ------ 

Subtask #1 : (10 points)

1 ≤ T ≤ 20
1 ≤ N, K ≤ 10

Subtask 2 : (20 points) 

1 ≤ T ≤ 10
1 ≤ N, K ≤ 10000

Subtask 3 : (70 points) 

1 ≤ T ≤ 100
1 ≤ N, K ≤ 10^{9}

----- Sample Input 1 ------ 
2
2 2
3 3
----- Sample Output 1 ------ 
2
12

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
Testcases = int(input())
for Testcase in range(0, Testcases):
	List = input().split()
	N = int(List[0])
	K = int(List[1])
	C = 10 ** 9 + 7
	Result = K * pow(K - 1, N - 1, C) % C
	print(Result)


MOD = 1000000007

def fast_exp(base, exp):
	res = 1
	while exp:
		if exp & 1:
			res = res * base % MOD
		base = base * base % MOD
		exp = exp >> 1
	return res
for t in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 1:
		if n == 1:
			print('1')
		else:
			print('0')
		continue
	ans = k
	ans = ans * fast_exp(k - 1, n - 1) % MOD
	print(ans)


m = 10 ** 9 + 7
for tt in range(int(input())):
	(n, k) = map(int, input().split())
	z = k - 1
	aa = k % m
	print(aa * pow(z, n - 1, m) % m)


t = int(input())
for i in range(1, t + 1):
	numbers = list(map(int, input().split()))
	n = numbers[0]
	k = numbers[1]
	k1 = k % (10 ** 9 + 7)
	k2 = pow(k - 1, n - 1, 10 ** 9 + 7)
	temp = k1 * k2 % (10 ** 9 + 7)
	print(temp)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(k * pow(k - 1, n - 1, 1000000007) % 1000000007)


t = int(input())
for i in range(t):
	(n, k) = tuple(map(int, input().split()))
	ans = pow(k - 1, n - 1, 1000000007)
	ans = ans % 1000000007 * (k % 1000000007) % 1000000007
	print(ans)


mod = 1000000007
for _ in range(int(input())):
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	print(k * pow(k - 1, n - 1, mod) % mod)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 1000000007
	print(k % mod * pow(k - 1, n - 1, mod) % mod)


def mod_pow(base, exp, mod):
	result = 1
	while exp:
		if exp & 1:
			result = result * base % mod
		exp >>= 1
		base = base * base % mod
	return result

def solve(n, k, mod):
	return k * mod_pow(k - 1, n - 1, mod) % mod
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k, 10 ** 9 + 7))


def pow_mod(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
t = int(input())
MOD = 10 ** 9 + 7
for _ in range(0, t):
	(n, k) = map(int, input().split())
	if k == 1:
		if n == 1:
			print(1)
		else:
			print(0)
	elif n == 1:
		if k == 1:
			print(1)
		else:
			print(n * k)
	else:
		ans = 1
		ans = k % MOD * int(pow_mod(k - 1, n - 1, MOD)) % MOD
		print(ans)


from sys import stdin as sin
t = int(sin.readline())
for _ in range(t):
	(n, k) = map(int, sin.readline().split())
	x = pow(k - 1, n - 1, 1000000007)
	x = x * k % 1000000007
	print(x)


a = int(input())
for i in range(a):
	(y, x) = map(int, input().split())
	print(x * pow(x - 1, y - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


mod = int(1000000007)

def pow1(x, y):
	temp = 0
	if y == 0:
		return 1
	temp = pow1(x, int(y / 2)) % mod
	if y % 2 == 0:
		temp = temp * temp % mod
		return temp
	else:
		temp = temp * temp % mod
		temp = x * temp % mod
		return temp
t = int(input())
while t != 0:
	t -= 1
	(x, y) = map(int, input().split())
	print(y * pow1(y - 1, x - 1) % mod)


t = int(input())
ans = []
for i in range(t):
	x = list(map(str, input().split()))
	n = int(x[0])
	k = int(x[1])
	temp_old = int(k % (10 ** 9 + 7) * pow(k - 1, n - 1, 10 ** 9 + 7) % (10 ** 9 + 7))
	ans.append(temp_old)
for x in ans:
	print(x)


def mult(n, k):
	if n == 0:
		return 1
	if n == 1:
		return k
	else:
		pcount = 1
		ans = k
		while True:
			if pcount * 2 > n:
				break
			ans = ans % constant * (ans % constant) % constant
			pcount = pcount * 2
		return ans % constant * (mult(n - pcount, k) % constant) % constant

def mult2(n, k):
	return pow(k, n, constant)
constant = pow(10, 9) + 7

def answer():
	for t in range(int(input())):
		(N, K) = [int(x) for x in input().split()]
		if N == 1:
			print(K)
		elif N != 1 and K == 1:
			print(0)
		elif N != 1 and K != 1:
			print(K * (mult(N - 1, K - 1) % constant) % constant)
	return
answer()


import math
import sys

def main():
	m = int(input())
	for i in range(1, m + 1, 1):
		(n, k) = map(int, sys.stdin.readline().split())
		to = 1
		to = pow(k - 1, n - 1, 1000000007)
		to = to * k % 1000000007
		print(to)
main()


md = int(1000000000.0 + 7)
T = int(input())
while T > 0:
	T -= 1
	(n, k) = map(int, input().split())
	ans = k * pow(k - 1, n - 1, md) % md
	print(ans)


for _ in range(int(input())):
	nk = [int(i) for i in input().split()]
	n = nk[0]
	k = nk[1]
	if n == 1 and k == 1:
		print(1)
		continue
	ans = k * pow(k - 1, n - 1, 1000000007) % 1000000007
	print(ans)


m = 10 ** 9 + 7

def Kode(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
for tt in range(int(input())):
	(n, k) = map(int, input().split())
	z = k - 1
	a = k % m * Kode(z, n - 1, m) % m
	print(a)


def fast_power(a, n):
	result = 1
	value = a
	power = n
	while power > 0:
		if power % 2 == 1:
			result = result * value % 1000000007
		value = value * value % 1000000007
		power = int(power // 2)
	return result
t = int(input())
while t > 0:
	x = input().split()
	n = int(x[0])
	k = int(x[1])
	ans = k * fast_power(k - 1, n - 1)
	print(ans % 1000000007)
	t = t - 1


import math
T = int(input())
for i in range(0, T):
	(a, b) = map(int, input().split())
	x = pow(b - 1, a - 1, 1000000007)
	x = x * b
	x = x % 1000000007
	print(x)


import math
T = int(input())
for i in range(0, T):
	(n, k) = map(int, input().split())
	a = pow(k - 1, n - 1, 1000000007)
	a = a * k % 1000000007
	print(a)


def f(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
import math
testCases = int(input())
for c in range(0, testCases):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	temp = f(k - 1, n - 1, 1000000007)
	temp2 = k % 1000000007
	answer = temp * temp2 % 1000000007
	print(answer)


import sys

def sq(x, n):
	if n == 0:
		return 1
	elif n == 1:
		if x > 10000007:
			return x % 1000000007
		return x
	elif n % 2 == 0:
		p = sq(x, n / 2)
		p *= p
		if p > 1000000007:
			return p % 1000000007
		return p
	else:
		p = sq(x, (n - 1) / 2)
		p *= p * x
		if p > 1000000007:
			return p % 1000000007
		return p
t = int(input())
while t:
	(n, k) = map(int, sys.stdin.readline().split())
	if n == 1:
		res = k
	elif k == 1:
		res = 0
	else:
		res = sq(k - 1, n - 1)
		res = res * k
	res = res % (1000000000 + 7)
	print(res, '\n')
	t = t - 1


M = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(m * pow(m - 1, n - 1, M) % M)


import sys

def long_pow(x, y, z):
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
test_cases = int(input())
for test in range(test_cases):
	(n, m) = map(int, input().split())
	ans = m * long_pow(m - 1, n - 1, 1000000007) % 1000000007
	print(ans)


def power(a, b, m):
	if a == 0:
		return 0
	if b == 0:
		return 1
	p = power(a, b // 2, m) % m
	p = p * p % m
	if b % 2 == 1:
		p = p * a % m
	return p
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	ans = power(k - 1, n - 1, 1000000007)
	ans = ans * k
	ans = ans % 1000000007
	print(ans)


def gao(x, y):
	if x == 1:
		return y
	if y == 1:
		return 0 if x > 1 else 1
	m = 10 ** 9 + 7

	def p(x, e):
		if e == 0:
			return 1
		q = p(x, e // 2)
		q = q * q % m
		return q * x % m if e % 2 == 1 else q
	return p(y - 1, x - 1) * y % m
n = int(input())
for _ in range(n):
	(x, y) = map(int, input().split())
	print(gao(x, y))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 10 ** 9 + 7
	ans = k % m * pow(k - 1, n - 1, m) % m
	print(ans)


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x
	elif y == -1:
		return 1 / float(x)
	elif y % 2 == 0:
		tmp = power(x, y // 2)
		return tmp * tmp
	else:
		tmp = power(x, y // 2)
		if y > 0:
			return x * tmp * tmp
		elif y == -3:
			return tmp / float(x)
		else:
			return tmp * tmp / float(x)

def main():
	t = int(input())
	for j in range(t):
		l = [int(i) for i in input().split()]
		(no, col) = (l[0], l[1])
		print(pow(col, 1, 1000000007) * pow(col - 1, no - 1, 1000000007) % 1000000007)
main()


def power(x, y):
	result = 1
	value = x
	power = y
	while power > 0:
		if power % 2 == 1:
			result = result * value
		value = value * value
		value = value % 1000000007
		power = power // 2
	return result
T = int(input())
while T > 0:
	(N, K) = map(int, input().split())
	ways = K
	temp = power(K - 1, N - 1)
	ways = ways * temp
	ways = ways % 1000000007
	print(ways)
	T = T - 1


x = int(input())
mod = 1000000007
for q in range(x):
	y = input().split(' ')
	n = int(y[0])
	k = int(y[1])
	ans = pow(k - 1, n - 1, mod)
	ans = k * ans % mod
	print(ans)


def power(x, y):
	if y == 0:
		return 1
	if y == 1:
		return x
	temp = power(x, y // 2)
	if y % 2 == 0:
		return temp * temp % 1000000007
	else:
		return x * temp * temp % 1000000007
t = int(input())
b = []
for i in range(0, t):
	a = []
	a = list(map(int, input().split()))
	tot = power(a[1] - 1, a[0] - 1)
	t = str(tot * a[1] % 1000000007)
	b.append(t)
print('\n'.join(b))


t = int(input())
mod = 1000000007
for T in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	ans = pow(k - 1, n - 1, mod)
	ans *= k
	ans %= mod
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	if k == 1 and n == 1:
		print(1)
	elif k == 1 and n > 1:
		print(0)
	else:
		print(pow(k - 1, n - 1, 1000000007) * k % 1000000007)


for y in range(int(input())):
	(N, K) = map(int, input().split())
	ans = K * pow(K - 1, N - 1, 1000000007) % 1000000007
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print(k * pow(k - 1, n - 1, 10 ** 9 + 7) % (10 ** 9 + 7))


def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x
	else:
		a = power(x, y // 2) % 1000000007
		if y % 2 == 0:
			return a * a % 1000000007
		else:
			return a * a * x % 1000000007
for i in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	p = power(k - 1, n - 1)
	ans = p * k
	print(ans % 1000000007)


mod = 1000000007
T = int(input())

def fun(n, k):
	a = k - 1
	b = n - 1
	ans = k
	while b != 0:
		if b % 2 == 1:
			ans = ans * a
			ans = ans % mod
		a = a * a
		a = a % mod
		b = b // 2
	return ans
for i in range(T):
	(n, k) = map(int, input().split())
	print(fun(n, k))


def modpow(b, e, mod):
	res = 1
	b %= mod
	while e:
		if e & 1:
			res = res * b % mod
		b = b * b % mod
		e >>= 1
	return res
t = int(input())
mod = int(1000000000.0) + 7
for i in range(t):
	(n, k) = map(int, input().split(' '))
	t = k * modpow(k - 1, n - 1, mod)
	t %= mod
	print(t)


t = int(input())
for case in range(t):
	(n, k) = map(int, input().split())
	m = 1000000007
	k = k * pow((k - 1) % m, (n - 1) % m, 1000000007)
	print(k % m)


t = int(input())
while t != 0:
	t = t - 1
	(n, k) = [int(y) for y in input().split()]
	ans = pow(k - 1, n - 1, 1000000007) * k % 1000000007
	print(ans)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	x = pow(k - 1, n - 1, 10 ** 9 + 7)
	y = k % (10 ** 9 + 7)
	print(x * y % (10 ** 9 + 7))
	t = t - 1


m = 1000000007

def multiply(n, k):
	if k == 0:
		return 1
	mul = multiply(n, k // 2) % m
	if k % 2 == 1:
		return n * mul * mul
	else:
		return mul * mul

def number(n, k):
	ans = k
	if n - 1 == 0:
		ans = ans * 1
	elif k - 1 == 0:
		ans = ans * 0
	else:
		ans = ans * multiply(k - 1, n - 1)
		ans = ans % m
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	print(number(n, k))


for i in range(int(input())):
	(x, y) = map(int, input().split())
	m = 10 ** 9 + 7
	ans = y % m * pow(y - 1, x - 1, m) % m
	print(ans)


prime = 10 ** 9 + 7
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	print(k % prime * pow(k - 1, n - 1, prime) % prime)
	t -= 1


for _ in range(int(input())):
	(m, n) = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	print(n * pow(n - 1, m - 1, mod) % mod)


def bipin3():

	def func(a, b):
		if b:
			if b & 1:
				return a * func(a, b - 1) % 1000000007
			else:
				k = a * a % 1000000007
				return k * func(k, b // 2 - 1) % 1000000007
		else:
			return 1
	test = int(input())
	while test:
		(z, k) = map(int, input().split())
		if z == 1:
			print(k)
		elif k == 1:
			print(0)
		else:
			print(k * func(k - 1, z - 1) % 1000000007)
		test -= 1
bipin3()


t = int(input())
while t:
	(n, k) = (int(x) for x in input().split())
	m = 10 ** 9 + 7
	ans = k % m * pow(k - 1, n - 1, m) % m
	print(ans)
	t = t - 1


def f(x, e, m):
	X = x
	E = e
	Y = 1
	while E > 0:
		if E % 2 == 0:
			X = X * X % m
			E = E / 2
		else:
			Y = X * Y % m
			E = E - 1
	return Y
for tests in range(int(input())):
	[N, K] = [int(i) for i in input().split()]
	N -= 1
	p = K
	p = p * f(K - 1, N, 10 ** 9 + 7) % (10 ** 9 + 7)
	print(p)


import sys
mod = 1000000007

def go(z):
	(n, k) = (z[0], z[1])
	ret = pow(k - 1, n - 1, mod) * k
	ret = ret % mod
	print(ret)
f = sys.stdin
n = int(f.readline().strip())
for i in range(n):
	z = [int(x) for x in f.readline().split()]
	go(z)


def MOD(x):
	return x % 1000000007

def bigMod(x, n):
	if n == 0:
		return 1
	ret = bigMod(x, n // 2)
	ret = MOD(ret * ret)
	if n % 2 == 1:
		ret = MOD(ret * x)
	return ret
t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	ans = MOD(bigMod(k - 1, n - 1) * k)
	print(ans)


def power(x, y):
	if y == 0:
		return 1
	temp = power(int(x), int(y / 2)) % 1000000007
	if y % 2 == 0:
		return temp * temp % 1000000007
	else:
		return x * temp * temp % 1000000007
t = int(input())
for i in range(t):
	a = [int(i) for i in input().split()]
	(m, k) = (a[0], a[1])
	(mm, kk) = (m - 1 % 1000000007, k - 1 % 1000000007)
	count = k * power(kk, mm)
	print(count % 1000000007)


import math
q = 1000000007

def fast_exp(base, exp):
	res = 1
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % q
		base = base * base % q
		exp //= 2
	return res
t = int(input())
while t:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	if n == 1:
		print(k)
		t -= 1
		continue
	p = k * fast_exp(k - 1, n - 1)
	print(int(p % q))
	t -= 1


test = int(input())
while test != 0:
	test -= 1
	(n, k) = map(int, input().split())
	m = pow(10, 9) + 7
	ans = k % m
	c = k - 1
	k = int(bin(n - 1)[2:])
	while k != 0:
		if k % 10 == 1:
			ans = ans * c % m
		k = k // 10
		c = c * c % m
	print(ans % m)


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	prod = k
	prod2 = pow(k - 1, n - 1, 1000000007)
	prod *= prod2
	prod %= 1000000007
	print(prod)


mod = 10 ** 9 + 7
t = int(input())
while t:
	(n, k) = map(int, input().split())
	sum = k
	sum *= pow(k - 1, n - 1, mod)
	sum %= mod
	print(sum)
	t -= 1


def power(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	count = k - 1
	mod = 10 ** 9 + 7
	ans = k
	ans = ans % mod * power(count, n - 1, mod) % mod % mod
	print(ans)


t = int(input())
mod = 1000000007
while t:
	num = input().split()
	n = int(num[0])
	m = int(num[1])
	a = 1
	b = m - 1
	n = n - 1
	while n > 0:
		if n % 2 != 0:
			a *= b
			a %= mod
		b *= b
		b %= mod
		n = n // 2
	sol = a * m % mod
	print(sol)
	t -= 1


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	ans = r * pow(r - 1, l - 1, 1000000007)
	ans %= 1000000007
	print(ans)


def fast_power(a, n):
	m = 1000000007
	result = 1
	value = a
	power = n
	while power > 0:
		if power % 2 == 1:
			result = result * value
			result = result % m
		value = value * value
		value = value % m
		power = power // 2
	return result
for t in range(int(input())):
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	if n > 1 and k == 1:
		print('0')
	else:
		m = 1000000007
		p = fast_power(k - 1, n - 1) % m
		print(k * p % m)


t = int(input())
for i in range(t):
	s = input().split(' ')
	x = int(s[0])
	y = int(s[1])
	m = 0
	if x == 1:
		m = y
	else:
		m = y * pow(y - 1, x - 1, 1000000007)
	print(m % 1000000007)


def power(a, b, n):
	r = 1
	while b > 0:
		if b & 1 == 1:
			r = r * a % n
		b = b // 2
		a = a * a % n
	return r % n
t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	x = k
	n -= 1
	k -= 1
	print(power(k, n, 1000000007) * x % 1000000007)


MOD = 1000000007

def PowMod(n, b):
	if n == 0 and b == 0:
		return 1
	ret = 1
	while n > 0:
		if n % 2 == 1:
			ret = ret * b % MOD
		b = b * b % MOD
		n >>= 1
	return ret
T = int(input())
for i in range(0, T):
	(N, K) = map(int, input().split(' '))
	print(K * PowMod(N - 1, K - 1) % MOD)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	ans = pow(k - 1, n - 1, 1000000007) * k % 1000000007
	print(ans)


memo = {}
M = pow(10, 9) + 7

def power(k, n):
	if n in memo:
		return memo
	if n == 0 or n == 1:
		return pow(k, n)
	if n % 2 == 0:
		a = power(k, n // 2) % M
		memo[n] = a * a % M
		return memo[n]
	else:
		a = power(k, (n - 1) // 2) % M
		memo[n] = a * a * k % M
		return memo[n]
t = int(input())
for i in range(t):
	memo = {}
	(n, k) = (int(x) for x in input().split())
	print(power(k - 1, n - 1) * k % M)


'__author__' == 'deepak Singh Mehta(learning to code :) ) '
mod = 1000000007

def pow(b, e, m):
	global mod
	c = 1
	while e:
		if e & 1:
			c = c * b % m
		e //= 2
		b = b * b % m
	return c
tests = int(input())
for _ in range(tests):
	(n, k) = map(int, input().split())
	ans = 0
	if k == 1 and n > 1:
		ans = 0
	else:
		ans = k
		ans = ans % mod * pow(k - 1, n - 1, mod) % mod
	print(ans)


import sys

def power(base, exp):
	if exp == 0:
		return 1
	if exp == 1:
		return base
	if exp % 2 == 0:
		half = power(base, exp / 2) % 1000000007
		return half * half % 1000000007
	else:
		half = power(base, (exp - 1) / 2)
		return base * (half * half % 1000000007) % 1000000007
num_of_test_cases = int(input())
while num_of_test_cases:
	configuration = str(input())
	num_zombie = int(configuration.split(' ')[0])
	num_colors = int(configuration.split(' ')[1])
	if num_zombie == 1:
		print(num_colors)
		num_of_test_cases -= 1
		continue
	res = int(num_colors * power(num_colors - 1, num_zombie - 1))
	res %= 1000000007
	print(res)
	num_of_test_cases -= 1


from sys import stdin
t = int(stdin.readline())
for i in range(t):
	(n, k) = map(int, stdin.readline().split())
	ans = pow(k - 1, n - 1, 1000000007) * k % 1000000007
	print(ans)