DCC intensive Care Contest (Replay)

Permutation is a mathematical notation means all possible arrangements of a collection of things, where the order is important.  For Example: You want to visit the homes of three friends Alex ("a"), Betty ("b") and Chandra ("c"), but haven't decided in what order. What choices do you have?

Answer: {a,b,c} {a,c,b} {b,a,c} {b,c,a} {c,a,b} {c,b,a}

If the order does not matter, it is a Combination.

There is also a weaker meaning of the term "permutation" that is sometimes used in elementary combinatory texts, designating those ordered arrangements in which no element occurs more than once, but without the requirement of using all the elements from a given set. These are not permutations except in special cases, but are natural generalizations of the ordered arrangement concept. Indeed this use often involves considering arrangements of a fixed length k of elements taken from a given set of size n. These objects are also known as partial permutations or as sequences without repetition, terms that avoid confusion with the other, more common, meaning of "permutation".

The number of such k-permutations of n is denoted variously by such symbols as _n P_k, ⁿP_k, P_n,k, or P(n,k), and its value is given by the product n*(n-1)*(n-2)............(n-k+1).

which is 0 when k > n, and otherwise is equal to

Input:

The first line of the input contains an integer T (≤ T ≤ 100) denoting the number of test cases. Each test case contains two space separated integers n and k. (0≤n, k≤1000)

Output:

For each case, print the case number and , ⁿP_k. And remember that answer should be modulo of (10^9+7).

Sample: