E. Count permutations
time limit per test
15 s
memory limit per test
1024 megabytes
input
permutations.in
output
standard output

We heard you like problems with short statements and no stories, this one is for you!

Count the number of permutations of length N where the maximum length of an increasing subarray is exactly K.

Input

The first line of input is the number of test cases T.

Each test case consists of a single line containing two integers N and K, where 1 ≤ K ≤ N ≤ 200.

Output

For each test case output a single line containing the answer to the problem modulo 109 + 7.

Example
Input
4
9 4
9 3
7 1
7 7
Output
60875
189524
1
1
Note
  • A permutation of length N is a sequence of all integers between 1 and N, where each integer appears exactly once and the numbers can appear in any order.
  • A subarray of array A is an array equals to [Ai, Ai + 1, Ai + 2, ..Aj] where 1 ≤ i ≤ j ≤ |A|.

  • For a permutation to be counted, it should have at least one increasing subarray of length K and there is no any increasing subarray with length greater than K.