405557: GYM101992 E Count permutations

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.

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.

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

4
9 4
9 3
7 1
7 7

60875
189524
1
1

• 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 [A_i, A_i + 1, A_i + 2, ..A_j] 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.