Migrated from Lutece 1395 Princes and Princesses

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Once upon a time there was a prince who wanted to marry a princess; but she would have to be a real princess. He travelled all over the world to find one, but nowhere could he get what he wanted. There were princesses enough, but it was difficult to find out whether they were real ones. There was always something about them that was not as it should be. So he came home again and was sad, for he would have liked very much to have a real princess.

One evening a terrible storm came on; there was thunder and lightning, and the rain poured down in torrents. Suddenly a knocking was heard at the city gate, and the old king went to open it.

It was a princess standing out there in front of the gate. But, good gracious! what a sight the rain and the wind had made her look. The water ran down from her hair and clothes; it ran down into the toes of her shoes and out again at the heels. And yet she said that she was a real princess.

Well, we'll soon find that out, thought the old queen. But she said nothing, went into the bed-room, took all the bedding off the bedstead, and laid a pea on the bottom; then she took twenty mattresses and laid them on the pea, and then twenty eider-down beds on top of the mattresses.

On this the princess had to lie all night. In the morning she was asked how she had slept.

"Oh, very badly!" said she. "I have scarcely closed my eyes all night. Heaven only knows what was in the bed, but I was lying on something hard, so that I am black and blue all over my body. It's horrible!"

Now they knew that she was a real princess because she had felt the pea right through the twenty mattresses and the twenty eider-down beds.

Nobody but a real princess could be as sensitive as that.

The prince took her for his wife, for now he knew that he had a real princess; and the pea was put in the museum, where it may still be seen, if no one has stolen it.

So the prince in order to express his love to the princess, so he decides to send roses to the princess. There are $K$ kinds of roses. And prince wants to select $N$ roses to places on the ground in a row. $The$ $prince$ $request$ $all$ $of$ $K$ $kinds$ $of$ $roses$ $must$ $appear$, and he wants to ask you there are how many ways to place the roses?

Input

The first line only contains an positive integer $T$ ( $T \leq 100$ ) , represents there are $T$ test cases.

For each test case:

The first line contains two positive integers $N$ and $K$. $1 \leq N \leq 5 * 10^4，1 \leq K \leq 30$

Output

For each test case, output in one line a positive integer, represents the number of ways to places N roses in a row,

the answer may be large, please output the answer $modulo$ $(772002+233)$.

Samples

2
1 1
3 2

1
6

Note

For the second test case , there are $6$ ways to places the roses: $(1,1,2) , (1,2,1) , (1,2,2)，(2,1,1)，(2,1,2)，(2,2,1)$

Resources

IEEEXTREME Programming Competition