Chef Dengklek will open a new restaurant in the city. The restaurant will be open for N days. He can cook M different types of dish. He would like to cook a single dish every day, such that for the entire N days, he only cook at most K distinct types of dishes.

In how many ways can he do that?

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

The first line contains a single integer T, the number of test cases. T test cases follow. Each test case consists of a single line consisting of three integers N, M, K.

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

For each test case, output a single line consisting the number of different ways he can cook for the entire N days, modulo 1000000007.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 1000$
$1 ≤ M ≤ 1000000$
$1 ≤ K ≤ 1000$

----- Sample Input 1 ------ 
4
1 1 1
2 2 2
4 3 2
5 7 3
----- Sample Output 1 ------ 
1
4
45
5887

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Combinatorics

Dynamic programming

Mathematics


Solutions:
MOD = 1000000007

def fill_nks(N, mod):
	nd = [[0 for j in range(N + 1)] for i in range(N + 1)]
	for i in range(N + 1):
		nd[i][0] = 1
		nd[i][1] = 1
	for n in range(1, N + 1):
		for k in range(2, n + 1):
			nd[n][k] = (nd[n - 1][k - 1] + k * nd[n - 1][k]) % mod
	return nd
KS = fill_nks(1000, MOD)

def dishes_exact_k(n, mpk, k, mod):
	return mpk * KS[n][k] % mod

def dishes(n, m, k, mod):
	k = min(n, m, k)
	res = 0
	mk = 1
	for i in range(1, k + 1):
		mk = mk * (m - i + 1) % mod
		kdishes = dishes_exact_k(n, mk, i, mod)
		res = (res + kdishes) % mod
	return res
test_case = int(input())
for test in range(test_case):
	(n, m, k) = map(int, input().split())
	print(dishes(n, m, k, MOD))


class Sol:

	@staticmethod
	def solver():
		T = int(input())
		mod = 1000000007
		dp = [[0] * 1001 for _ in range(1001)]
		dp[0][0] = 1
		for day in range(1, 1001):
			for dish in range(1, day + 1):
				dp[day][dish] = (dp[day - 1][dish - 1] + dp[day - 1][dish] * dish) % mod
		while T:
			T -= 1
			(n, m, k) = list(map(int, input().split(' ')))
			k = m if k > m else n if k > n else k
			factorial = 1
			total = 0
			for dishes in range(1, k + 1):
				factorial = factorial * (m - dishes + 1) % mod
				total = (factorial * dp[n][dishes] + total) % mod
			print(total)
Sol.solver()


MOD = 1000000007

def fill_nks(N, mod):
	nks = [[0 for j in range(N + 1)] for i in range(N + 1)]
	for i in range(N + 1):
		nks[i][0] = 1
		nks[i][1] = 1
	for n in range(1, N + 1):
		for k in range(2, n + 1):
			nks[n][k] = (nks[n - 1][k - 1] + k * nks[n - 1][k]) % mod
	return nks
NKS = fill_nks(1000, MOD)

def dishes_exact_k(n, mpk, k, mod):
	return mpk * NKS[n][k] % mod

def dishes(n, m, k, mod):
	k = min(n, m, k)
	res = 0
	mpk = 1
	for i in range(1, k + 1):
		mpk = mpk * (m - i + 1) % mod
		kdishes = dishes_exact_k(n, mpk, i, mod)
		res = (res + kdishes) % mod
	return res
t = int(input().strip())
for _ in range(t):
	(n, m, k) = (int(i.strip()) for i in input().split())
	print(dishes(n, m, k, MOD))


mod = 1000000007
dp = [[0] * 1001 for _ in range(1001)]
dp[0][0] = 1
for day in range(1, 1001):
	for dish in range(1, day + 1):
		dp[day][dish] = (dp[day - 1][dish - 1] + dp[day - 1][dish] * dish) % mod
for _ in range(int(input())):
	(n, m, k) = list(map(int, input().split()))
	k = m if k > m else n if k > n else k
	factorial = 1
	total = 0
	for dishes in range(1, k + 1):
		factorial = factorial * (m - dishes + 1) % mod
		total = (factorial * dp[n][dishes] + total) % mod
	print(total)