You are given two integers, $N$ and $\mbox{M}$. Count the number of strings of length $N$ (under the alphabet set of size $\mbox{M}$) that doesn't contain any palindromic string of the length greater than $\mbox{1}$ as a consecutive substring.

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, ${T}$, the number of test cases.

Then there will be ${T}$ lines, each containing two space-separated integers, $N$ and $\mbox{M}$, denoting a single test case. The meanings of $N$ and $\mbox{M}$ are described in the Problem Statement above.

Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo $10^9+7$.

Constraints  

$1\leq T\leq10^5$

$1\leq N,M\leq10^9$

Sample Input
2
2 2
2 3

Sample Output
2
6

Explanation

For the 1^{st} testcase, we have an alphabet of size M = 2. For the sake of simplicity, let's consider the alphabet as [A, B]. We can construct four strings of size N = 2 using these letters.

AA
AB
BA
BB

Out of these, we have two strings, AB and BA, that satisfy the condition of not having a palindromic string of length greater than 1. Hence, the answer 2.

For the 2^{nd} test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters. 

AA
AB
AC
BA
BB
BC
CA
CB
CC

Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(f(n, m))


i = int(input())
for j in range(i):
	(a, b) = map(int, input().split(' '))
	if b == 2:
		if a == 1:
			print(b)
		elif a == 2:
			print(2)
		else:
			print(0)
	elif a == 1:
		print(b)
	elif b == 1:
		print(0)
	else:
		print(b * (b - 1) * pow(b - 2, a - 2, 10 ** 9 + 7) % (10 ** 9 + 7))


modulus = 1000000007

def powermod(b, e, m):
	val = 1
	while e > 0:
		if e & 1 == 1:
			val = val * b % m
		e = e // 2
		b = b * b % m
	return val
t = int(input())
for i in range(0, t):
	(N, M) = map(int, input().split())
	if N == 1:
		print(M)
	elif N == 2:
		print(M * (M - 1) % modulus)
	else:
		print(M * (M - 1) * powermod(M - 2, N - 2, modulus) % modulus)


t = int(input())
for j in range(t):
	s = list(map(int, input().strip().split()))
	n = s[0]
	m = s[1]
	p = int(1000000000.0 + 7)
	if m == 1:
		if n > 1:
			ans = 0
		else:
			ans = 1
	elif m == 2:
		if n > 2:
			ans = 0
		else:
			ans = 2
	elif n > 2:
		ans = m * (m - 1) * pow(m - 2, n - 2, p)
	elif n == 2:
		ans = m * (m - 1) % p
	else:
		ans = m
	print(ans % p)


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


modulo = 10 ** 9 + 7
numTests = int(input())
for test in range(numTests):
	(n, m) = [int(n) for n in input().split(' ')]
	if n == 1:
		print(m % modulo)
	elif n == 2:
		print(m * (m - 1) % modulo)
	else:
		print(m * (m - 1) * pow(m - 2, n - 2, modulo) % modulo)


P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(f(n, m))


_MOD = 10 ** 9 + 7

def num_antipal(n, m):
	if n == 1:
		return m % _MOD
	elif n == 2:
		return m * (m - 1) % _MOD
	return m * (m - 1) * pow(m - 2, n - 2, _MOD) % _MOD
t = int(input())
for _ in range(t):
	(n, m) = [int(el) for el in input().split()]
	print(num_antipal(n, m))


t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	if n == 1:
		print(m)
	elif n == 2:
		print(m * (m - 1) % 1000000007)
	else:
		temp = m * (m - 1) % 1000000007
		(a, b, res) = (m - 2, n - 2, 1)
		while b:
			if b % 2:
				res = res * a % 1000000007
			a = a * a % 1000000007
			b = b // 2
		print(temp * res % 1000000007)


from itertools import product
modulo = 10 ** 9 + 7

def anti(m, n):
	if n == 1:
		return m
	elif n == 2:
		return (m - 1) * m % modulo
	else:
		return pow(m - 2, n - 2, modulo) * anti(m, 2) % modulo
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(anti(m, n))


modulus = 1000000007

def largepower(base, exp, modulus):
	if exp % 2 == 1:
		answer = base % modulus
	else:
		answer = 1
	multiplier = base % modulus
	exp //= 2
	while exp != 0:
		multiplier = multiplier ** 2 % modulus
		if exp % 2 == 1:
			answer = answer * multiplier % modulus
		exp //= 2
	return answer
T = int(input())
for tc in range(T):
	nm = input().split()
	N = int(nm[0])
	M = int(nm[1])
	if N == 1:
		print(M)
	elif N == 2:
		print(M * (M - 1) % modulus)
	else:
		result = M * (M - 1) % modulus
		result = result * largepower(M - 2, N - 2, 1000000007) % modulus
		print(result)


P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(f(n, m))


def main():
	MOD = 10 ** 9 + 7
	ncases = int(input())
	for case in range(ncases):
		(strlen, alphasize) = [int(f) for f in input().split()]
		if strlen == 1:
			print(alphasize)
		else:
			print(alphasize * (alphasize - 1) * pow(alphasize - 2, strlen - 2, MOD) % MOD)
main()


MOD = 10 ** 9 + 7

def solve(N, M):
	if N == 1:
		return M % MOD
	else:
		return M * (M - 1) * pow(M - 2, N - 2, MOD) % MOD
T = int(input())
for _ in range(T):
	(N, M) = (int(_) for _ in input().split())
	print(solve(N, M))


mod = 1000000007

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

def anti_palindromic_strings(N, M):
	if N == 1:
		return M % mod
	result = M * (M - 1) % mod
	result = result * modpow(M - 2, N - 2) % mod
	return result
T = int(input())
for _ in range(T):
	(N, M) = [int(i) for i in input().split()]
	print(anti_palindromic_strings(N, M))


def count_antipalindromic(n, m):
	if n == 1:
		return m % (10 ** 9 + 7)
	elif n == 2:
		return m * (m - 1) % (10 ** 9 + 7)
	else:
		tmp = pow(m - 2, n - 2, 10 ** 9 + 7)
		return m * (m - 1) * tmp % (10 ** 9 + 7)

def main():
	t = int(input())
	for p in range(t):
		(n, m) = map(int, input().split())
		print(count_antipalindromic(n, m))
main()


M = 10 ** 9 + 7

def calc_power(x, y):
	if y == 0:
		return 1
	if y % 2 == 1:
		return x * calc_power(x, y - 1) % M
	else:
		t = calc_power(x, y // 2)
		return t * t % M
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	ans = m
	if n >= 2:
		ans *= m - 1
		ans *= calc_power(m - 2, n - 2)
	print(ans % M)


def soBig(x, time):
	if time == 1:
		return x
	if time == 2:
		return x * x
	if time % 2 == 1:
		return x * soBig(x, time - 1) % (10 ** 9 + 7)
	tt = soBig(x, time // 2) % (10 ** 9 + 7)
	return tt * tt % (10 ** 9 + 7)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	ans = m
	if n >= 2:
		ans *= m - 1
	if n >= 3:
		time = n - 2
		ans = ans * soBig(m - 2, time) % (10 ** 9 + 7)
	print(ans % (10 ** 9 + 7))


def main():
	num_cases = int(input().strip())
	num = pow(10, 9) + 7
	for i in range(num_cases):
		(n, m) = (int(i) for i in input().strip().split(' '))
		if n == 1:
			num_antipalins = m
		elif m == 1:
			num_antipalins = 0
		else:
			num_antipalins = pow(m - 2, n - 2, num) * m * (m - 1) % num
		print(num_antipalins)
main()


def antipalindromic(slength, alength):
	mod = 1000000007
	value = alength
	value %= mod
	if slength > 1:
		value *= alength - 1
		value %= mod
		value *= pow(alength - 2, slength - 2, mod)
		value %= mod
	return value

def main():
	T = int(input())
	for _ in range(T):
		print(antipalindromic(*[int(i) for i in input().split()]))
main()


def exp_mod_p(n, k, p):
	if k == 0:
		return 1
	elif k == 1:
		return n
	elif k % 2 == 1:
		return n * exp_mod_p(n, k - 1, p) % p
	else:
		sqrt = exp_mod_p(n, k // 2, p)
		return sqrt * sqrt % p
p = 1000000007
for test in range(0, int(input())):
	(str_len, alphabet_size) = map(int, input().split())
	if str_len == 1:
		print(alphabet_size)
	elif str_len == 2:
		print(alphabet_size * (alphabet_size - 1) % p)
	else:
		count = alphabet_size * (alphabet_size - 1) % p
		count = count * exp_mod_p(alphabet_size - 2, str_len - 2, p) % p
		print(count)


def MyPow(x, p):
	if p == 0:
		return 1
	elif p == 1:
		return x
	elif p & 1:
		return x * MyPow(x ** 2 % (10 ** 9 + 7), (p - 1) // 2) % (10 ** 9 + 7)
	else:
		return MyPow(x ** 2 % (10 ** 9 + 7), p // 2) % (10 ** 9 + 7)
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	if N < 2:
		print(M)
		continue
	else:
		r = M * (M - 1) % (10 ** 9 + 7)
		r *= MyPow(M - 2, N - 2)
		r %= 10 ** 9 + 7
	print(r)


t = int(input())
for i in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	if m <= 2 and n > m:
		valor = 0
	elif n == 1:
		valor = m
	else:
		valor = m * max(m - 1, 1) * pow(max(m - 2, 1), n - 2, pow(10, 9) + 7)
	print(valor % (pow(10, 9) + 7))


for t in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	if n >= 2:
		print(pow(m - 2, n - 2, 10 ** 9 + 7) * m * (m - 1) % (10 ** 9 + 7))
	elif n == 1:
		print(m)


def modPow(x, y, m):
	if y == 0:
		return 1
	if y == 1:
		return x
	temp = modPow(x, y // 2, m)
	if y % 2 == 0:
		return temp * temp % m
	else:
		return temp * temp % m * x % m
t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	if n == 1:
		print(m)
		continue
	elif n == 2:
		print(m * (m - 1) % (10 ** 9 + 7))
		continue
	res = m * (m - 1) % (10 ** 9 + 7)
	res = res * modPow(m - 2, n - 2, 10 ** 9 + 7) % (10 ** 9 + 7)
	print(res)


mod_number = 10 ** 9 + 7
for _ in range(int(input())):
	(length_of_string, size_of_alphabet) = [int(x) for x in input().split()]
	number_of_possible_strings = size_of_alphabet
	if length_of_string > 1:
		number_of_possible_strings *= size_of_alphabet - 1
	if length_of_string > 2:
		number_of_possible_strings *= pow(size_of_alphabet - 2, length_of_string - 2, mod_number)
	print(number_of_possible_strings % mod_number)


def calc_antipal(m, n):
	if n == 1:
		return m
	if m == 1:
		return 0
	i = m * (m - 1) * pow(m - 2, n - 2, 1000000007)
	return i % 1000000007
t = int(input())
for i in range(t):
	(n, m) = input().split()
	print(calc_antipal(int(m), int(n)))


import math
i = int(input())
for j in range(i):
	w = input().split()
	n = int(w[0])
	m = int(w[1])
	a = 1
	t = 1
	if n == 1:
		a = m
	elif m == 1:
		a = 0
	elif n == 2:
		a = m * (m - 1)
	elif m == 2:
		a = 0
	else:
		a = int(int(m * (m - 1) * pow(m - 2, n - 2, pow(10, 9) + 7)))
	print(pow(a, 1, pow(10, 9) + 7))


cases = int(input())
modulus = 10 ** 9 + 7

def exp(base, exponent):
	if exponent == 0:
		return 1
	elif exponent % 2 == 0:
		root = exp(base, exponent // 2) % modulus
		return root * root % modulus
	else:
		first = base % modulus
		rest = exp(base, exponent - 1) % modulus
		return first * rest % modulus
for _ in range(cases):
	(word_length, alphabet_size) = [int(x) for x in input().split()]
	if word_length == 1:
		antipalindromes = alphabet_size
	else:
		antipalindromes = alphabet_size
		antipalindromes *= alphabet_size - 1
		antipalindromes *= exp(alphabet_size - 2, word_length - 2)
		antipalindromes %= modulus
	print(antipalindromes)


T = int(input())
MOD = 10 ** 9 + 7
for i in range(0, T):
	lists = input().split()
	N = int(lists[0])
	M = int(lists[1])
	ans = M
	if N > 1:
		ans = ans * (M - 1)
	if N > 2:
		ans = ans * pow(M - 2, N - 2, MOD)
		ans = ans % MOD
	print(int(ans % MOD))


t = int(input())
MOD = 10 ** 9 + 7
for i in range(t):
	(N, M) = (int(x) for x in input().strip().split(' '))
	s = M
	if N > 1:
		s *= M - 1
	if N > 2:
		s *= pow(M - 2, N - 2, MOD)
		s %= MOD
	print(s % MOD)


from fileinput import input
mod = 1000000007

def find():
	lines = input()
	noc = [int(x) for x in lines[0].strip().split()][0]
	for i in range(1, 1 + noc):
		(n, m) = [int(x) for x in lines[i].strip().split()]
		print(check(n, m), end='\n')

def check(n, m):
	if n == 1:
		return m % mod
	if n == 2:
		return m * (m - 1) % mod
	valid1 = m * (m - 1) * mpn(n - 2, m - 2) % mod
	return valid1 % mod

def mpn(n, m):
	if n == 0:
		return 1
	if n == 1:
		return m % mod
	half = mpn(n // 2, m)
	tmp = half * half % mod
	if n & 1 == 0:
		return tmp
	else:
		return tmp * m % mod
find()


def f(n, m):
	p = m
	if n == 1:
		return p
	p = p * (m - 1) % 1000000007
	if n == 2:
		return p
	k = m - 2
	p2 = pow(k, n - 2, 1000000007)
	p = p * p2 % 1000000007
	return p
for t in range(int(input())):
	(n, m) = [int(i) for i in input().split(' ')]
	print(f(n, m))


def powX(a, p):
	x = 1
	for i in range(p):
		x = x * a % 1000000007
	return x
t = int(input())
for j in range(t):
	(n, m) = [int(i) for i in input().split(' ')]
	if n == 1:
		answer = m
	elif n == 2:
		answer = m * (m - 1) % 1000000007
	elif n == 3:
		answer = m * (m - 1) * (m - 2) % 1000000007
	elif n > 3:
		answer = m * (m - 1) * pow(m - 2, n - 2, 1000000007) % 1000000007
	print(answer)


P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(f(n, m))


testcases = int(input().strip())
mmod = 10 ** 9 + 7
for case in range(testcases):
	(n, m) = [int(x) for x in input().strip().split()]
	if n == 1:
		print(m % mmod)
	else:
		print(m * (m - 1) * pow(m - 2, n - 2, mmod) % mmod)


p = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(m * (m - 1) * pow(m - 2, n - 2, p) % p if n > 1 else m)


P = 10 ** 9 + 7

def foo(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	print(foo(n, m))


T = int(input())
modulo = 10 ** 9 + 7
for cnt in range(T):
	[N, M] = list(map(int, input().strip().split()))
	if N == 1:
		print(M)
		continue
	prod = M * (M - 1)
	prod %= modulo
	expo = N - 2
	power = M - 2
	while expo > 0:
		if expo & 1 == 1:
			prod *= power
			prod %= modulo
		power *= power
		power %= modulo
		expo >>= 1
	print(prod)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n > 2:
		cnt = m * (m - 1)
		m -= 2
		n -= 2
		while n > 1:
			if n & 1:
				cnt = cnt * m % 1000000007
				m = m * m % 1000000007
				n = (n - 1) // 2
			else:
				m = m * m % 1000000007
				n = n // 2
		print(cnt * m % 1000000007)
	elif n == 2:
		print(m * (m - 1) % 1000000007)
	else:
		print(m % 1000000007)


from sys import stdin
t = int(stdin.readline())
z = 1000000000 + 7
for ti in range(t):
	(n, m) = tuple((int(x) for x in stdin.readline().split()))
	if n == 0:
		print(1)
	elif n == 1:
		print(m % z)
	else:
		print(m * (m - 1) * pow(m - 2, n - 2, z) % z)


modulus = 10 ** 9 + 7
t = int(input().strip())
for i in range(t):
	(n, m) = [int(j) for j in input().strip().split(' ')]
	if n == 1:
		print(m)
		continue
	product = pow(m - 2, n - 2, modulus)
	product *= m * (m - 1)
	product %= modulus
	print(product)


md = 1000000007
t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	r = 1
	if n >= 2:
		r = pow(m - 2, n - 2, md)
		r *= m - 1
	r *= m
	print(r % md)


t = int(input().strip())
mod = 10 ** 9 + 7
for _ in range(t):
	(n, m) = [int(x) for x in input().split(' ')]
	x = m
	if n == 1:
		x = m
	elif n == 2:
		x = m * m - m
	else:
		x = m * (m - 1) * pow(m - 2, n - 2, mod)
	print(x % mod)


MOD = 1000000007

def solve():
	(N, M) = input().strip().split(' ')
	N = int(N)
	M = int(M)
	ans = int(1)
	if N == 1:
		ans = M
	else:
		if M >= 2:
			ans = pow(M - 2, N - 2, MOD)
		ans = ans * M * (M - 1)
		ans %= MOD
	print(ans)

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


MOD = int(1000000000.0 + 7)
for xx in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		print(m)
		continue
	if n == 2:
		print(m * (m - 1) % MOD)
		continue
	ans = m * (m - 1) % MOD
	n -= 2
	print(ans * pow(m - 2, n, MOD) % MOD)


import math
MODU = int(7 + 1000000000.0)

def fast_pow(base, n, M=MODU):
	if n == 0:
		return 1
	elif n == 1:
		return base
	half_n = fast_pow(base, n // 2, M)
	if not n % 2:
		return half_n * half_n % M
	else:
		return half_n * half_n % M * base % M

def number_of_non_palindromic(N, M):
	if N == 1:
		return M
	ret = M * (M - 1) % MODU
	if N > 2:
		ret = ret * fast_pow(M - 2, N - 2) % MODU
	return ret
x = int(input())
for i in range(0, x):
	args = tuple([int(x) for x in input().split(' ')])
	print(number_of_non_palindromic(*args))


Modulus = 10 ** 9 + 7

def antiPalindrome(n, k):
	if n == 1:
		return k % Modulus
	if n == 2:
		return k * (k - 1) % Modulus
	else:
		return k * (k - 1) * pow(k - 2, n - 2, Modulus) % Modulus
N = int(input())
for _ in range(N):
	(n, k) = [int(x) for x in input().split()]
	print(antiPalindrome(n, k))


import sys

def anti_palandromes(n, m):
	if n == 1:
		return m
	return m * (m - 1) * pow(m - 2, n - 2, 1000000007) % 1000000007
lines = sys.stdin.readlines()
ntests = int(lines[0].strip())
t = 0
for li in lines[1:]:
	(N, M) = map(int, li.strip().split(' '))
	print(anti_palandromes(N, M))
	t += 1
	if t == ntests:
		break


Q = 10 ** 9 + 7

def mul_in_Q(x, y):
	return x * y % Q

def pow_in_Q(x, y):
	x %= Q
	accum = 1
	x_tt_i = x
	i = 1
	while y > 0:
		if y % 2 ** i != 0:
			accum *= x_tt_i
			accum %= Q
			y -= y % 2 ** i
		(x_tt_i, i) = (x_tt_i * x_tt_i % Q, i + 1)
	return accum
for _ in range(int(input().strip())):
	(N, M) = map(int, input().strip().split(' '))
	if N == 1:
		print(M % Q)
	else:
		print(M * (M - 1) * pow_in_Q(M - 2, N - 2) % Q)


import sys
tc_len = int(sys.stdin.readline())
for tc in range(tc_len):
	(n, m) = tuple((int(x) for x in sys.stdin.readline().split()))
	modulo = int(1000000000.0 + 7)
	if n == 1:
		print(str(m % modulo))
	else:
		print(str(m * (m - 1) * pow(m - 2, n - 2, modulo) % modulo))


from sys import stdin
modo = 10 ** 9 + 7

def faire(M, N):
	return M * (M - 1) * pow(M - 2, N - 2, modo) % modo
nbcas = int(input().strip())
for _ in range(nbcas):
	lig = input().strip().split()
	(N, M) = (int(z) for z in lig)
	if M > 999999000:
		print(1 / 0)
	if N == 1:
		print(M % modo)
	elif N == 2:
		print(M * (M - 1) % modo)
	elif M == 1:
		print(0)
	else:
		print(faire(M, N))


MOD_NUM = 10 ** 9 + 7

def run():
	(N, M) = map(int, input().strip().split())
	if N == 1:
		return M
	if N == 2:
		return M * (M - 1) % MOD_NUM
	if M <= 2:
		return 0
	M1 = M * (M - 1) % MOD_NUM
	M2N2 = pow(M - 2, N - 2, MOD_NUM)
	return M1 * M2N2 % MOD_NUM
T = int(input())
for _ in range(T):
	print(run())


modulus = 10 ** 9 + 7

def num_antipal_strs(n, m):
	if n == 0:
		return 1
	elif n == 1:
		return m
	else:
		return m * (m - 1) * pow(m - 2, n - 2, modulus) % modulus
num_test_cases = int(input())
for _ in range(num_test_cases):
	(n, m) = [int(s) for s in input().split()]
	print(num_antipal_strs(n, m))


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	r = M
	if N > 1:
		r *= (M - 1) * pow(M - 2, N - 2, 10 ** 9 + 7)
	print(r % (10 ** 9 + 7))


def mod_pow(x, y, p):
	res = 1
	x = x % p
	while y > 0:
		if y % 2 == 1:
			res = res * x % p
		y = y // 2
		x = x * x % p
	return res
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	if n == 1:
		print(m)
	else:
		combos = m * (m - 1)
		if m >= 2 and n >= 3:
			combos *= mod_pow(m - 2, n - 2, 10 ** 9 + 7)
		print(combos % (10 ** 9 + 7))


P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(f(n, m))


import sys

def mod_exp(base, expo, mod):
	result = 1
	while expo > 0:
		if expo % 2 == 1:
			result = result * base % mod
		expo = int(expo) >> 1
		base = base * base % mod
	return result
num_tests = int(input().strip())
modulus = 10 ** 9 + 7
for i in range(num_tests):
	(n, m) = [int(x) for x in input().strip().split()]
	if n == 0:
		print(1)
	elif n == 1:
		print(m)
	else:
		print(m * (m - 1) * mod_exp(m - 2, n - 2, modulus) % modulus)


P = 10 ** 9 + 7

def f(n, m):
	if n == 1:
		return m % P
	if n == 2:
		return m * (m - 1) % P
	if m <= 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, P) % P
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(f(n, m))


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


p = 10 ** 9 + 7
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		print(m)
	else:
		print(m * (m - 1) * pow(m - 2, n - 2, p) % p)


magicmod = 10 ** 9 + 7
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	if N == 1:
		res = M
	else:
		res = M * (M - 1) * pow(M - 2, N - 2, magicmod) % magicmod
	print(res)


import sys

def getAntiPalindromes(n, m):
	if n == 1:
		return m % modulo
	elif n == 2:
		return m * (m - 1) % modulo
	else:
		return m * (m - 1) * pow(m - 2, n - 2, modulo) % modulo
t = eval(sys.stdin.readline())
modulo = 10 ** 9 + 7
for i in range(t):
	(n, m) = map(int, input().split())
	print(getAntiPalindromes(n, m))


P = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	t = 1
	if n > 0:
		t *= m
	if n > 1:
		t = t * (m - 1) % P
	y = m - 2
	(x, p) = (n - 2, y)
	while 1 <= x:
		if x & 1 == 1:
			x -= 1
			t = t * p % P
		else:
			x //= 2
			p = p * p % P
	print(t)


modulus = 10 ** 9 + 7

def count_antipalindromic(n, m):
	if n == 1:
		return m % modulus
	if m == 1:
		return 0
	if n == 2:
		return m * (m - 1) % modulus
	if m == 2:
		return 0
	return m * (m - 1) * pow(m - 2, n - 2, modulus) % modulus

def process_routine():
	T = int(input())
	for _ in range(T):
		(N, M) = map(int, input().split())
		print(count_antipalindromic(N, M))
process_routine()


for i in range(int(input())):
	(N, M) = map(int, input().split())
	if N == 1:
		print(M)
	elif M == 1:
		print(0)
	else:
		print(pow(M - 2, N - 2, 1000000007) * (M - 1) * M % 1000000007)


def fastexp(x, n, mod):
	if x == 0:
		return 0
	else:
		result = 1
		power = x
		while n > 0:
			if n % 2 == 1:
				result = result * power % mod
			power = power * power % mod
			n = n // 2
		return result
mod = 10 ** 9 + 7
t = int(input())
for i in range(t):
	(length, alphabetSize) = map(int, input().split())
	if alphabetSize >= 2 and length > 2:
		print(alphabetSize * (alphabetSize - 1) * fastexp(alphabetSize - 2, length - 2, mod) % mod)
	elif alphabetSize >= 2 and length <= 2:
		if length == 2:
			print(alphabetSize * (alphabetSize - 1) % mod)
		elif length == 1:
			print(alphabetSize)
	elif alphabetSize == 1 and length > 2:
		if length == 1:
			print(alphabetSize)
		else:
			print(0)
	elif alphabetSize < 2 and length <= 2:
		if length == 2:
			print(0)
		elif length == 1:
			print(alphabetSize)


import sys
from time import time

def solve(n, m, modulo):
	if n == 1:
		return m % modulo
	rval = m * (m - 1) % modulo
	c = m * (m - 1) // 2
	rval *= pow(m - 2, n - 2, modulo)
	return rval % modulo
tm = time()
modulo = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m, modulo))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


import string
t = input().strip()
MOD = 10 ** 9 + 7
for i in range(int(t)):
	(N, M) = input().strip().split(' ')
	M = int(M)
	N = int(N)
	s = M
	if N > 1:
		s *= M - 1
	if N > 2:
		s *= pow(M - 2, N - 2, MOD)
		s %= MOD
	print(s % MOD)


T = int(input())

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 t0 in range(T):
	(N, M) = (int(a) for a in input().split())
	if N == 1:
		ans = M
	elif N == 2:
		ans = M * (M - 1)
	else:
		ans = M * (M - 1) * pow(M - 2, N - 2, 10 ** 9 + 7)
	ans = ans % (10 ** 9 + 7)
	print(ans)


import sys
MOD = 1000000007
T = int(input().strip())
for i in range(T):
	(N, M) = map(int, sys.stdin.readline().split())
	if N > 2:
		t = pow(M - 2, N - 2, MOD) * M * (M - 1)
	elif N == 2:
		t = M * (M - 1)
	else:
		t = M
	print(t % MOD)


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


def pwr(b, e):
	global MOD
	b %= MOD
	if e == 0:
		return 1
	if e == 1:
		return b
	return pwr(b * b, e // 2) * pwr(b, e % 2) % MOD
MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		print(m)
	elif n == 2:
		print(m * (m - 1) % MOD)
	else:
		print(m * (m - 1) * pwr(m - 2, n - 2) % MOD)


MOD = 10 ** 9 + 7
from sys import stdin
readl = stdin.readline
for _ in range(int(readl())):
	(n, m) = map(int, readl().split())
	r = m
	if n > 1:
		r *= m - 1
		r *= pow(m - 2, n - 2, MOD)
	if r >= MOD:
		r %= MOD
	print(r)


K = 10 ** 9 + 7

def C(n, m):
	c = m % K
	if n < 2:
		return c
	c *= (m - 1) % K
	if n < 3:
		return c % K
	if m < 3:
		return 0
	f = (m - 2) % K
	for i in map(int, reversed('{:b}'.format(n - 2))):
		if i:
			c = c * f % K
		f = f * f % K
	return c % K
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(C(n, m))


t = int(input())
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	mod = 10 ** 9 + 7
	if n == 1:
		print(m % mod)
	elif n == 2:
		print(m * (m - 1) % mod)
	else:
		res = m * (m - 1)
		i = n - 2
		base = m - 2
		while i > 0:
			if i % 2 == 1:
				res *= base
				res %= mod
			base = base ** 2 % mod
			i >>= 1
		print(res)


MOD = 10 ** 9 + 7
T = int(input())
for run in range(T):
	(N, M) = [int(i) for i in input().split()]
	if N == 1:
		print(M % MOD)
	else:
		p = 1
		e = N - 2
		a = M - 2
		while e > 0:
			if e % 2 == 1:
				p = p * a % MOD
			e //= 2
			a = a * a % MOD
		print(M * (M - 1) * p % MOD)


t = int(input())
x = 1000000007
while t:
	t -= 1
	(n, m) = map(int, input().split())
	if n == 1:
		print(m)
	else:
		print(m % x * (m - 1) % x % x * pow(m - 2, n - 2, x) % x)


def bitize(x):
	L = []
	while x > 0:
		L.append(x % 2)
		x //= 2
	if not L:
		L = [0]
	return L

def pow_mod(a, b, m):
	b_bits = bitize(b)
	a_powers = [0 for x in b_bits]
	a_powers[0] = a % m
	if b_bits[0]:
		total = a % m
	else:
		total = 1
	for i in range(1, len(b_bits)):
		a_powers[i] = a_powers[i - 1] * a_powers[i - 1] % m
		if b_bits[i]:
			total *= a_powers[i]
			total %= m
	return total

def compute_anti_palindromes(N, M, modulus):
	ans = M * (M - 1) % modulus
	if N == 1:
		return M % modulus
	elif N == 2:
		return M * (M - 1) % modulus
	else:
		ans *= pow_mod(M - 2, N - 2, modulus)
	return ans % modulus
T = int(input())
modulus = pow(10, 9) + 7
for _ in range(0, T):
	(N, M) = [int(a) for a in input().split()]
	print(compute_anti_palindromes(N, M, modulus))


t = int(input())
for _ in range(t):
	(n, m) = [int(s) for s in input().split()]
	if n == 1:
		print(m)
	else:
		result = m * (m - 1) * pow(m - 2, n - 2, int(1000000000.0 + 7)) % int(1000000000.0 + 7)
		print(result)


mod = 1000000007

def modpow(a, p):
	if p == 0:
		return 1
	if p == 1:
		return a % mod
	if p % 2 == 1:
		return modpow(a % mod * a % mod % mod, p // 2) % mod * a % mod % mod
	return modpow(a % mod * a % mod % mod, p // 2) % mod

def solve(m, n):
	if n == 1:
		return m
	return m % mod * ((m - 1) % mod) % mod * modpow(m - 2, max(0, n - 2)) % mod % mod
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(solve(m, n))


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

def nb_strings(length, alphabet):
	modulate = 1000000007
	if length == 1:
		return alphabet % modulate
	if length == 2:
		return alphabet * (alphabet - 1) % modulate
	val = alphabet * (alphabet - 1) % modulate
	val = val * pow_mod(alphabet - 2, length - 2, modulate) % modulate
	return val

def process():
	nb_tests = int(input())
	for _ in range(nb_tests):
		(length, alphabet) = map(int, input().split())
		print(nb_strings(length, alphabet))
process()


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


import os
import sys

def solve(n, m):
	if m == 1 and n == 1:
		return 1
	elif m == 1 and n > 1:
		return 0
	elif n == 1:
		return m
	return int(m * (m - 1) * pow(m - 2, n - 2, 1000000007) % 1000000007)
t = int(input())
for t_itr in range(t):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	result = solve(n, m)
	print(str(result))


P = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	if N == 1:
		res = M
	else:
		res = M * (M - 1) * pow(M - 2, N - 2, P) % P
	print(res)


M = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		print(m % M)
	elif n == 2:
		print(m * (m - 1) % M)
	else:
		print(pow(m - 2, n - 2, M) * (m * (m - 1)) % M)