Magic Toy Brick

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$\left(1\leq h\leq m \right)$. 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.

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\left(1\leq n\leq 1000 \right)$ and $m\left(1\leq m\leq 100000 \right)$, representing the number of bricks and the maximal height of toy bricks.

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

2
1 1
2 2

Case #1: 1
Case #2: 7

there are seven shapes in the second test case.$(x,y)$ indicates
that No.$x$'s height is $y$.
1、(1,1)(2,1)

2、(1,1)(2,2)

3、(1,2)(2,2)  

4、(1,1)
(2,1)

5、(1,1)
(2,2)

6、(1,2)
(2,1)

7、(1,2)
(2,2)

BestCoder Round #38 ($)