You are given integers $N$ and $K$, where $N$ is the number of points on the x-axis and $K$ is the number of available colors $(1, 2 .. K)$ of a butterfly.

You want to place these butterflies on the x-axis next to each other such that no butterfly of the same color is sitting adjacent. Also, there is another integer $X$ which means butterflies of color $X$ are allowed to sit adjacent to each other.

Find the number of such possible arrangements mod $10^9 + 7$

Input format

• First line of input: Contains $T$, where $T$ is number of test cases.
• For every test case: The first line contains $N$, $K$, and $X$, where N is the number of points, $K$ is the number of colors available, and $X$ is the color of the butterfly that is allowed to sit adjacent.

Note: $X$ can be greater than $K$.

Output

For every test case print the number of arrangements mod $10^9 + 7$

Constraints

$1 \leq N \leq 10^5$

$1 \leq X, K \leq 5$