Kevin calls a permutation perfect if the following conditions holds:

• Permutation consists of N elements.
• Permutation has K inversions.
• Number of inversions isn't bigger than number of elements in permutation (\(K \le N\)).

Kevin is interested in how many perfect permutations exist. As this number can be very big output it modulo \(1000000007 (10^9 + 7)\).

Input format:

The first line of input will contain an integer T, denoting the number of test cases.
Each of the next T lines contain two integers N and K.

Output format:

For every test case output the number of perfect permutations modulo \(10^9+7\).

Constraints:

• \(1 \le T \le 100\)
• \(K \le N\)
• (10 points): \(1 \le N \le 8, 0 \le K \le 8\)
• (10 points): \(1 \le N \le 50, 0 \le K \le 50\)
• (20 points): \(1 \le N \le 1000, 0 \le K \le 1000\)
• (20 points): \(1 \le N \le 10^9, 0 \le K \le 1000\)
• (20 points): \(1 \le N \le 10^9, 0 \le K \le 10^5, T = 1\)
• (20 points): \(1 \le N \le 10^9, 0 \le K \le 10^5\)