E. Sorting Cards
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Today is a great day at Uncling University. We have a new grand uncle! After two years of training at Uncleforces, Uncle Jaber has finally become a granduncle. He is very happy now!

There is a law at Uncling University: once you become a granduncle, you have to give a lecture about uncling.

As a troublemaker, Attal wants to ask a provocative question during the lecture. He will ask about a problem. Yes, he wants to discuss a problem from the last gym he participated in. Hosen is attending the lecture and he gets angry when someone discusses a problem from a gym. But if Jaber solves it before him, he will calm down and forget about it. You have to help Jaber solve the problem as fast as possible to avoid Hosen's rage.

Here is the problem:

We have an infinite number of playing cards, each card having a number between $$$1$$$ and $$$M$$$, and a color between $$$1$$$ and $$$K$$$.

You have to count the number of ways to choose a stack $$$A$$$ of $$$N$$$ cards such that the resulting stack $$$B$$$ is good.

Stack $$$B$$$ is obtained in the following way:

  1. Stack $$$B$$$ is initially empty.
  2. If stack $$$A$$$ is empty, we are done.
  3. Take the card from the top of stack $$$A$$$ and put it in your hand (then the card is removed from $$$A$$$).
  4. If stack $$$B$$$ is empty, put the card on the top of stack $$$B$$$. Otherwise, if the color of the card in your hand and the color of the card on the top of stack $$$B$$$ are different, then put the card in your hand on the top of stack $$$B$$$; otherwise, throw it away.
  5. Return to step 2.
Stack $$$B$$$ is good if the numbers written on the cards from the top to the bottom are sorted in non-decreasing order.

Two stacks of size $$$N$$$ are considered different if and only if there is an integer $$$i$$$ such that the $$$i_{th}$$$ card from the top in the first stack differs from the $$$i_{th}$$$ card from the top in the second one.

Two cards are considered different if they have different numbers or colors.

As the number may be very large, you are asked to print it modulo $$$10^9 + 7$$$.

Input

The first line of input contains a single $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.

Each of the next T lines contains three positive integers $$$N, M, K$$$ $$$(1 \le N,M,K \le 10^5)$$$, the size of the Stack $$$A$$$, the maximum number of a card, and the maximum color of a card respectively.

It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

Output the number of ways to choose a stack $$$A$$$ of $$$N$$$ cards such that the resulting stack $$$B$$$ is good modulo $$$10^9 + 7$$$.

Example
Input
3
1 1 1
2 2 2
3 1 2
Output
1
14
8