We define the following:

A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of array $[1,2,3]$ are $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{2,3\}$, $\{1,3\}$, and $\{1,2,3\}$.
The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in increasing order.

Victoria has two integers, $m$ and $n$. She builds unique arrays satisfying the following criteria:

Each array contains $m$ integers.
Each integer is $\in[1,n]$.
The longest increasing subsequence she can create from the array has length $n$.

Given ${p}$ pairs of $m$ and $n$ values, print the number of arrays Victoria creates for each pair on a new line. As this number can be quite large, print your answer modulo $(10^9+7)$.

Input Format

The first line contains a single positive integer, ${p}$, denoting the number of pairs. 

Each line ${i}$ of the ${p}$ subsequent lines contains two space-separated integers describing the respective $m$ and $n$ values for a pair.

Constraints

$1\leq p\leq50$
$1\leq m\leq5\times10^5$
$1\leq n\leq10^5$
$n\leq m$

Output Format

On a new line for each pair, print a single integer denoting the number of different arrays Victoria creates modulo $(10^9+7)$.

Sample Input
2
4 2
4 3

Sample Output
11
9

Explanation

Victoria wants to build arrays of integers having size $m=4$ where each integer is $\in\{1,2\}$ and each array has a longest increasing subsequence of length $n=2$ (i.e., contains the subsequence $\{1,2\}$). She creates the following eleven arrays: 
$1.[1,1,1,2]$
$2.[1,1,2,1]$
$3.[1,1,2,2]$
$4.[1,2,1,1]$
$5.[1,2,1,2]$
$6.[1,2,2,1]$ 
$7.[1,2,2,2]$ 
$8.[2,1,1,2]$
$9.[2,1,2,1]$
$10.[2,1,2,2]$
$11.[2,2,1,2]$
Victoria wants to build arrays of integers having size $m=4$ where each integer is $\in\{1,2,3\}$ and each array has a longest increasing subsequence of length $n=3$ (i.e., contains the subsequence $\{1,2,3\}$). She creates the following nine arrays:
$1.[1,1,2,3]$
$2.[1,2,1,3]$
$3.[1,2,2,3]$
$4.[1,2,3,1]$
$5.[1,2,3,2]$
$6.[1,2,3,3]$
$7.[1,3,2,3]$
$8.[2,1,2,3]$
$9.[3,1,2,3]$

Source: hackerrank | Difficulty: MEDIUM
Tags: Combinatorics


Solutions:
import os, sys, math

def modular_power(a, n, m):
	if n == 0:
		return 1
	a = a % m
	if a < 0:
		a += m
	prod = 1
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = prod * pwr % m
		n >>= 1
		if n == 0:
			break
		pwr = pwr * pwr % m
	return prod
MOD_INVERSE_CACHE = {}

def modular_inverse_cached(a, m):
	y = MOD_INVERSE_CACHE.get(m, {}).get(a)
	if y is None:
		y = modular_inverse(a, m)
		if m not in MOD_INVERSE_CACHE:
			MOD_INVERSE_CACHE[m] = {}
		MOD_INVERSE_CACHE[m][a] = y
	return y

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def solve1_basic(nmax, kmax):
	modulus = 10 ** 9 + 7
	A = [0] * (kmax + 1)
	A[0] = kmax - 1
	A[1] = 1
	for n in range(2, nmax + 1):
		t = A[0]
		A[0] = A[0] * (kmax - 1) % modulus
		for k in range(1, min(n, kmax) + 1):
			c = max(k, kmax - 1)
			(t, A[k]) = (A[k], (c * A[k] + t) % modulus)
	return A[kmax]

def solve1(n, a):
	modulus = 10 ** 9 + 7
	f = (a - 1) * modular_inverse_cached(a, modulus) % modulus
	t = 1
	s = 1
	for k in range(a, n):
		t = t * k * f * modular_inverse_cached(k - a + 1, modulus) % modulus
		s = (s + t) % modulus
	s = modular_power(f, a - 1, modulus) * s % modulus
	a1inv = modular_inverse_cached(a - 1, modulus)
	return modular_power(a, n - 1, modulus) * modular_power(a1inv, a - 1, modulus) * s % modulus

def solve(cases):
	for (n, k) in cases:
		print(solve1(n, k))

def main():
	t = int(sys.stdin.readline())
	cases = []
	for _ in range(t):
		(n, k) = list(map(int, sys.stdin.readline().split()))
		cases.append([n, k])
	solve(cases)
main()


import os, sys, math

def modular_power(a, n, m):
	if n == 0:
		return 1
	a = a % m
	if a < 0:
		a += m
	prod = 1
	pwr = a
	while n != 0:
		if n % 2 != 0:
			prod = prod * pwr % m
		n >>= 1
		if n == 0:
			break
		pwr = pwr * pwr % m
	return prod
MOD_INVERSE_CACHE = {}

def modular_inverse_cached(a, m):
	y = MOD_INVERSE_CACHE.get(m, {}).get(a)
	if y is None:
		y = modular_inverse(a, m)
		if m not in MOD_INVERSE_CACHE:
			MOD_INVERSE_CACHE[m] = {}
		MOD_INVERSE_CACHE[m][a] = y
	return y

def modular_inverse(a, m):
	m0 = m
	y = 0
	x = 1
	if m == 1:
		return 0
	while a > 1:
		q = a // m
		t = m
		m = a % m
		a = t
		t = y
		y = x - q * y
		x = t
	if x < 0:
		x = x + m0
	return x

def solve1_basic(nmax, kmax):
	modulus = 10 ** 9 + 7
	A = [0] * (kmax + 1)
	A[0] = kmax - 1
	A[1] = 1
	for n in range(2, nmax + 1):
		t = A[0]
		A[0] = A[0] * (kmax - 1) % modulus
		for k in range(1, min(n, kmax) + 1):
			c = max(k, kmax - 1)
			(t, A[k]) = (A[k], (c * A[k] + t) % modulus)
	return A[kmax]

def solve1(n, a):
	modulus = 10 ** 9 + 7
	f = (a - 1) * modular_inverse_cached(a, modulus) % modulus
	t = 1
	s = 1
	for k in range(a, n):
		t = t * k * f * modular_inverse_cached(k - a + 1, modulus) % modulus
		s = (s + t) % modulus
	s = modular_power(f, a - 1, modulus) * s % modulus
	a1inv = modular_inverse_cached(a - 1, modulus)
	return modular_power(a, n - 1, modulus) * modular_power(a1inv, a - 1, modulus) * s % modulus

def solve(cases):
	for (n, k) in cases:
		print(solve1(n, k))

def main():
	t = int(sys.stdin.readline())
	cases = []
	for _ in range(t):
		(n, k) = list(map(int, sys.stdin.readline().split()))
		cases.append([n, k])
	solve(cases)
main()