As we all know, F.C. Barcelona is the best soccer team of our era! Their entangling and mesmerizing game style usually translates into very high ball possession, consecutive counter-attack plays and goals. Lots of goals, thanks to the natural talent of their attacker and best player in history, Lionel Andres Messi.
However, at the most prestigious tournament of individual teams, the UEFA Champions League, there are no guarantees and believe it or not, Barcelona is in trouble.... They are tied versus Chelsea, which is a very defending team that usually relies on counter-strike to catch opposing teams off guard and we are in the last minute of the match. So Messi decided to settle things down for good and now he is conducting the ball on his teams' midfield and he will start a lethal counter-attack :D
After dribbling the 2 strikers from Chelsea, he now finds himself near the center of the field and he won't be able to dribble the entire team on his own, so he will need to pass the ball to one of his teammates, run forward and receive the ball once again to score the final goal.
Exactly K players are with him on his counter-attack and the coach, Tito Villanova knows that this counter-attack will end in a goal only if after exactly N passes are performed between the players, Messi ends up with the ball.
(Note that the ball only needs to end with Messi after exactly N passes are performed between all the K+1 players, i.e. Messi can receive the ball several times during the N passes. See the 2nd test case explanation for further clarification. ) 
However, he realized that there are many scenarios possible for this, so he asked you, his assistant coach, to tell him in how many ways can Messi score the important victory goal. So help him!!

-----Input-----
Input will contain a number T denoting the number of test cases.
Then T test cases follow, each one consisting of two space-sparated integers N and K.

-----Output-----
For each test case, output a single integer, the number of ways the winning play might happen modulo 1000000007 (109+7).

-----Constraints-----

- 1 ≤ T ≤ 100
- 2 ≤ N ≤ 1000
- 1 ≤ K ≤ 10

-----Example-----
Input:
2
2 4
4 2

Output:
4
6

-----Explanation-----
In the first test case, say four players with Messi are Xavi, Busquets, Iniesta and Jordi Alba. Then the ways of the winning play to happen when exactly  2 passes are to be performed are:
1) Messi - Xavi - Messi
2) Messi - Busquets - Messi
3) Messi - Iniesta - Messi
4) Messi - Alba - Messi

In the second test case, also say that two players with Messi are Xavi and Iniesta. There are 6 ways for the winning play to happen when exactly 4 passes are performed. All the examples of such winning play are:
1) Messi - Xavi - Messi - Iniesta - Messi
2) Messi - Xavi - Iniesta - Xavi - Messi
3) Messi - Xavi - Messi - Xavi - Messi
4) Messi - Iniesta - Messi - Iniesta - Messi
5) Messi - Iniesta - Messi - Xavi - Messi
6) Messi - Iniesta - Xavi - Iniesta - Messi

Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	sum = 0
	z = 0
	while n > 1:
		sum += k ** (n - 1) * (-1) ** z
		n -= 1
		z += 1
	print(sum % 1000000007)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	dp = [[0, 1]]
	for i in range(n - 1):
		dp.append([dp[-1][0] * (k - 1) + dp[-1][1] * k, dp[-1][0]])
	print(dp[-1][0] % 1000000007)


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = (k ** n + k * (-1) ** n) // (k + 1)
	print(ans % mod)


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	dp = [0] * N
	num_players = K + 1
	num_passes = N - 1
	for i in range(1, N):
		dp[i] = (num_players - 1) ** i - dp[i - 1]
	print(dp[-1] % 1000000007)


mod = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ls = [0] * (n + 1)
	(ls[0], ls[1]) = (1, 0)
	for i in range(2, n + 1):
		ls[i] = ((k - 1) * ls[i - 1] + k * ls[i - 2]) % mod
	print(ls[n])


m = 10 ** 9 + 7
for t in range(int(input())):
	(n, k) = map(int, input().split())
	if n == 2:
		print(k)
	elif n == 3:
		print(k * (k - 1))
	else:
		a = []
		a.append(0)
		a.append(0)
		a.append(k)
		a.append(k * (k - 1))
		i = 4
		while i <= n:
			val = (k - 1) * a[i - 1] % m
			val += k * a[i - 2] % m
			val %= m
			a.append(val)
			i += 1
		print(a[-1])


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	j = (k ** n + k * (-1) ** n) // (k + 1)
	j = j % 1000000007
	print(j)
	t -= 1


s = pow(10, 9) + 7
a = [[0 for i in range(11)] for j in range(1001)]
for i in range(1, 11):
	a[2][i] = i
for n in range(3, 1001):
	for k in range(1, 11):
		a[n][k] = pow(k, n - 1, s) - a[n - 1][k]
		if a[n][k] < 0:
			a[n][k] += s
t = int(input())
for i in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	print(a[n][k])


t = int(input())
if t >= 1 and t <= 100:
	while t > 0:
		(n, k) = input().split()
		n = int(n)
		k = int(k)
		if n >= 2 and n <= 1000 and (k >= 1) and (k <= 10):
			j = 1
			i = 2
			while i <= n:
				if i != 2:
					if i % 2 != 0:
						j = j * k - 1
					else:
						j = j * k + 1
				i = i + 1
			print(k * j % 1000000007)
		t = t - 1


for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	A = [[1], [0]]
	for i in range(1, n + 1):
		A[0].append(k * A[1][i - 1])
		A[1].append(A[0][i - 1] + (k - 1) * A[1][i - 1])
	print(A[0][n] % (10 ** 9 + 7))


def pulverize(a, b):
	apair = [1, 0]
	bpair = [0, 1]
	while True:
		if b == 0:
			return (a, apair[0], apair[1])
		else:
			q = a // b
			a -= b * q
			apair[0] -= bpair[0] * q
			apair[1] -= bpair[1] * q
		if a == 0:
			return (b, bpair[0], bpair[1])
		else:
			q = b // a
			b -= a * q
			bpair[0] -= apair[0] * q
			bpair[1] -= apair[1] * q

def inverse(a, m):
	(g, x, y) = pulverize(a, m)
	if g == 1:
		return x % m
	else:
		return 0
mbase = 10 ** 9 + 7

def main():
	t = int(input())
	for it in range(t):
		(n, k) = [int(x) for x in input().split()]
		res = pow(k, n, mbase)
		if n % 2 == 0:
			res += k
		else:
			res -= k
		res = res * inverse(k + 1, mbase) % mbase
		print(res)
main()


final = []
for j in range(2, 11):
	li = []
	li.append(0)
	li.append(0)
	li.append(j)
	for i in range(3, 1001):
		li.append(j * li[i - 2] + (j - 1) * li[i - 1])
		li[i] = li[i] % 1000000007
	final.append(li)
from sys import stdin
t = int(input())
for i in range(t):
	(n, k) = map(int, stdin.readline().split(' '))
	if k == 1:
		if n % 2 == 0:
			print(1)
		else:
			print(0)
	else:
		print(final[k - 2][n])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	c = k
	s = 0
	ans = k
	if n <= 1:
		print('0')
		continue
	for j in range(n - 1):
		s = c
		ans *= k
		c = ans - s
	print(s % 1000000007)


import sys
t = int(input())

def power(a, b):
	p = 1
	while b > 0:
		p = p * a % 1000000007
		p = p % 1000000007
		b = b - 1
	p = p % 1000000007
	return p
while t > 0:
	a = sys.stdin.readline().split()
	(n, k) = (int(a[0]), int(a[1]))
	messi = 0
	players = 0
	i = 1
	w = 1
	if n % 2 == 0:
		o = 1
	else:
		o = -1
	while i < n - 2:
		w = w * k % 1000000007
		messi += o * w
		messi = messi % 1000000007
		o *= -1
		i = i + 1
	players = power(k, n - 2) % 1000000007
	ans = ((players - messi) * (k - 1) % 1000000007 + messi * k % 10000000007) % 1000000007
	if n == 2:
		ans = k
	ans = ans % 1000000007
	print(ans)
	t = t - 1


T = int(input())
for _ in range(T):
	(p, n) = map(int, input().split())
	mod = 1000000007
	if p == 2:
		print(n)
	else:
		f = n
		t = n
		for i in range(p - 2):
			f = f % mod * n % mod
			a = (f - t + mod) % mod
			t = a
		print(a)


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(n, index):
	if (n, index) in m:
		return m[n, index]
	if n == 0:
		if index == k:
			return 1
		else:
			return 0
	res = 0
	for j in range(k + 1):
		if index != j:
			res = (res + dfs(n - 1, j)) % mod
	m[n, index] = res
	return res
t = int(input())
mod = 10 ** 9 + 7
for i in range(t):
	(n, k) = map(int, input().split())
	m = {}
	ans = dfs(n, k)
	print(ans)


t = int(input())
for k in range(t):
	(passes, players) = map(int, input().split())
	players += 1
	dp = [[0 for i in range(players)] for j in range(passes)]
	for i in range(1, players):
		dp[0][i] = 1
	prev_sum = players - 1
	for i in range(1, passes):
		cur_sum = 0
		for j in range(players):
			dp[i][j] = prev_sum - dp[i - 1][j]
			cur_sum += dp[i][j]
		prev_sum = cur_sum % (10 ** 9 + 7)
	print(dp[passes - 1][0] % (10 ** 9 + 7))


import sys

def win(player, passleft, dp):
	if (player, passleft) in dp:
		return dp[player, passleft]
	if passleft == 0 and player == 0:
		return 1
	elif passleft == 0 and player != 0:
		return 0
	dp[player, passleft] = 0
	for p in players:
		if p != player:
			dp[player, passleft] += win(p, passleft - 1, dp)
	dp[player, passleft] = dp[player, passleft] % 1000000007
	return dp[player, passleft]
sys.setrecursionlimit(1500)
t = int(input())
for _ in range(t):
	(passes, nop) = list(map(int, input().split()))
	players = [i for i in range(nop + 1)]
	print(win(0, passes, {}))


import sys

def passes(N, K):
	res = 0
	alt = 1
	for i in range(1, N):
		res += alt * K ** i
		alt = -alt
	return abs(res) % 1000000007

def process(input):
	nb_of_cases = int(input.readline().rstrip())
	for n in range(1, nb_of_cases + 1):
		(N, K) = (int(i) for i in input.readline().rstrip().split())
		answer = passes(N, K)
		print(answer)
input_file = sys.stdin
process(input_file)


mod = 1000000007

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

def string_list():
	return list(map(str, input().split()))

def hetro_list():
	return list(input().split())
import math
import sys
from collections import Counter, defaultdict

def main():
	dp = [[0, 0] for i in range(p + 1)]
	dp[0][0] = 1
	for i in range(1, p + 1):
		dp[i][0] = dp[i - 1][1] * k % mod
		dp[i][1] = dp[i - 1][1] * (k - 1) % mod + dp[i - 1][0] % mod
	print(dp[p][0] % mod)
t = int(input())
for _ in range(t):
	(p, k) = integer_list()
	main()


t = int(input())
for i in range(t):
	arr = input()
	l = list(map(int, arr.split(' ')))
	n = l[0]
	k = l[1]
	f = []
	f.append(k)
	f.append(k * (k - 1))
	if n == 2:
		print(f[0] % 1000000007)
	if n == 3:
		print(f[-1] % 1000000007)
	if n > 3:
		for j in range(n - 3):
			f.append(f[-2] * k + (k - 1) * f[-1])
		print(f[-1] % 1000000007)


MD = 10 ** 9 + 7
for _ in range(int(input())):
	st = input().split()
	N = int(st[0])
	K = int(st[1])
	M = 0
	B = K
	for k in range(N - 1):
		(M, B) = (B, (K * M + (K - 1) * B) % MD)
	print(M)


MOD = 1000000007

def main():
	t = int(input())
	for i in range(t):
		(a, b) = map(int, input().split())
		solve(a, b)

def solve(p, n):
	cache = [0] * (p + 1)
	cache[0] = 0
	cache[1] = 0
	cache[2] = 1
	for i in range(3, p + 1):
		cache[i] = (n ** (i - 2) % MOD - cache[i - 1]) % MOD
	print(n * cache[p] % MOD)
main()


import sys
sys.setrecursionlimit(3 * 10 ** 5)

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

def fun(n, k):
	modulo = 10 ** 9 + 7
	if n == 0:
		return 1
	return (power(k, n - 1, modulo) - fun(n - 1, k) % modulo + modulo) % modulo
for _ in range(int(input())):
	(n, k) = inum()
	if k == 1:
		if n % 2 == 0:
			print(1)
		else:
			print(0)
	elif n == 2:
		print(k)
	else:
		print(fun(n, k) % modulo)


mod = 1000000007

def powmod(k, n):
	if n == 0:
		return 1
	if n == 1:
		return k
	if n % 2 == 1:
		return k * powmod(k * k % mod, (n - 1) / 2) % mod
	else:
		return powmod(k * k % mod, n / 2) % mod
t = int(input())
while t:
	t -= 1
	line = input().split()
	n = int(line[0])
	k = int(line[1])
	invmod = powmod(k + 1, mod - 2)
	if n % 2 == 0:
		ans = (powmod(k, n) + k) * invmod % mod
	else:
		ans = (powmod(k, n) + mod - k) * invmod % mod
	print(ans)


e = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	messi = 0
	non_messi = k
	for i in range(n - 2):
		z = non_messi
		non_messi = (messi * k + z * (k - 1)) % e
		messi = z
	print(non_messi)


T = int(input())
counter = 0
while counter < T:
	(n, k) = map(int, input().split())
	currpos = 0
	non_zeroes = k
	zeroes = 0
	ans = k
	if n <= 1:
		print('0')
		continue
	for i in range(0, n - 1):
		zeroes = non_zeroes
		ans = ans * k
		non_zeroes = ans - zeroes
	print(zeroes % 1000000007)
	counter += 1


n = int(input())
for i in range(0, n):
	(k, p) = list(map(int, input().split(' ')))
	if k == 2:
		print(p)
	else:
		mess = [0] * (k + 1)
		nonmess = [0] * (k + 1)
		nonmess[1] = p
		for i in range(2, k):
			mess[i] = nonmess[i - 1]
			nonmess[i] = mess[i - 1] * p + nonmess[i - 1] * (p - 1)
		print(nonmess[k - 1] % 1000000007)


t = int(input())
while t:
	(n, k) = [int(x) for x in input().split()]
	table = list()
	table = [0 for x in range(n + 1)]
	table[0] = 1
	table[1] = 0
	for i in range(1, n):
		table[i + 1] = (table[i - 1] * k + table[i] * (k - 1)) % 1000000007
	print(table[n])
	t = t - 1