Problem Description
Today is Young F's 3rd birthday. His father gives him a set of magic toy bricks as a birthday gift, which contains a total of n bricks identified from 1 to n. Young F can set the height of every brick as an arbitrary integer h, which ranges from 1 to m(1≤h≤m). Young F loves the gift, and then he has fun with the bricks according to the following steps.
(1)step 1: take the No.1 toy brick, set its height h1 arbitrarily, place it at the beginning of the first row.
(2)step i (assuming there has been r rows formed by the previous i−1 toy bricks):take the No.i toy brick, and there are two operations which Young F can take:
(I) set its height hi arbitrarily, place No.i toy brick at the beginning of the r+1 row to create a new row(row r+1)
(II)select an arbitrary row from the existed r rows, set the height of new brick hi so that hi must be not less than the height of the last toy brick of selected row, then append No.i toy block to the selected row.
(3) operation ends when n toy blocks are used out, and the whole bricks can form a certain shape.
Young F is curious about how many different shapes will be formed with the whole bricks in all possible operations.
For two shapes, if the number of the rows is same, and the number of the bricks in corresponding row is also same, and the ID as well as the height of the brick at the corresponding position is still same, the two shapes are considered as the same shape.
Input
Multiple test cases, the first line contains an integer T(no more than 50), indicating the number of cases.Each test case contains two integer n(1≤n≤1000) and m(1≤m≤100000), representing the number of bricks and the maximal height of toy bricks.
Output
For each case，the output should occupies exactly one line. The output format is Case #x: ans, here x is the data number begins at 1, ans is the total number mod 1000000007.
Sample Input
2
1 1
2 2
Sample Output
Case #1: 1
Case #2: 7
