P17454 Iterated Fixed Points / Iterated Fixed Points

**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 $$ f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}. $$ Let $f^k$ denote the $k$-th iteration of the function $f$. If $x\in\{1,2,\ldots,n\}$ satisfies $$ f^k(x)=x, $$ 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$.

**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$.

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

Translated by ChatGPT 5