We define the following:
- A subsequence of an array is an ordered subset of the array's elements having the same sequential ordering as the original array. For example, the subsequences of array are , , , , , , and .
- The longest increasing subsequence of an array of numbers is the longest possible subsequence that can be created from its elements such that all elements are in increasing order.
Victoria has two integers, and . She builds unique arrays satisfying the following criteria:
- Each array contains integers.
- Each integer is .
- The longest increasing subsequence she can create from the array has length .
Given pairs of and values, print the number of arrays Victoria creates for each pair on a new line. As this number can be quite large, print your answer modulo .
Input Format
The first line contains a single positive integer, , denoting the number of pairs.
Each line of the subsequent lines contains two space-separated integers describing the respective and values for a pair.
Constraints
Output Format
On a new line for each pair, print a single integer denoting the number of different arrays Victoria creates modulo .
Sample Input
2
4 2
4 3
Sample Output
11
9
Explanation
- Victoria wants to build arrays of integers having size where each integer is and each array has a longest increasing subsequence of length (i.e., contains the subsequence ). She creates the following eleven arrays:
- Victoria wants to build arrays of integers having size where each integer is and each array has a longest increasing subsequence of length (i.e., contains the subsequence ). She creates the following nine arrays: