Problem Description

Due to differences in the performance of the judging machines, the time limit of this problem has been adjusted to 2 s.

Given three integers $n,k,p$.

Consider all functions

Let $f^k$ denote the $k$-th iteration of the function $f$. If $x\in\{1,2,\ldots,n\}$ satisfies

then $x$ is called a $k$-th order iterated fixed point of $f$.

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

Input Format

This problem contains multiple test cases.

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

The next $T$ lines each contain three integers $n,k,p$ $(1\le n,k\le 10^6,0\le p\le n)$.

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

Output Format

For each test case, output one integer per line, representing the result modulo $10^9+7$.

7
3 2 2
2 1 0
3 1 0
3 2 0
3 3 3
4 2 4
4 1 2

12
1
8
2
3
10
54

Hint

Translated by ChatGPT 5