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\)