405557: GYM101992 E Count permutations

Memory Limit:1024 MB Time Limit:9 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Count permutationstime limit per test9 secondsmemory limit per test1024 megabytesinputpermutations.inoutputstandard 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.

ExampleInput
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.

加入题单

上一题 下一题 算法标签: