M. Iterated Fixed Points
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$, an integer $$$k$$$, and an integer $$$p$$$.

Consider all functions $$$$$$ f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}. $$$$$$

Let $$$f^k$$$ denote the $$$k$$$-fold iteration of $$$f$$$. If $$$x \in \{1, 2, \dots, n\}$$$ satisfies $$$f^k(x) = x$$$, then $$$x$$$ is called a fixed point of $$$f^k$$$.

Find the number of functions $$$f$$$ that have exactly $$$p$$$ fixed points under $$$f^k$$$. Output the answer modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases.

The first line contains an integer $$$T$$$ $$$(1\le T\le10^4)$$$, the number of test cases.

Each of the next $$$T$$$ lines contains three integers $$$n,k,p$$$ $$$(1\le n,k\le10^6,\ 0\le p\le n)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer on a separate line, denoting the answer modulo $$$10^9+7$$$.

Example
Input
7
3 2 2
2 1 0
3 1 0
3 2 0
3 3 3
4 2 4
4 1 2
Output
12
1
8
2
3
10
54