P17454 迭代不动点 / Iterated Fixed Points

**由于评测机性能差异，本题时限调整至 2s**。 给定三个整数 $n,k,p$。 考虑所有函数 $$ f:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}. $$ 记 $f^k$ 表示函数 $f$ 的 $k$ 次迭代。若 $x\in\{1,2,\ldots,n\}$ 满足 $$ f^k(x)=x, $$ 则称 $x$ 是 $f$ 的一个 **$k$ 阶迭代不动点**。 求恰好有 $p$ 个 $k$ 阶迭代不动点的函数 $f$ 的数量。答案对 $10^9+7$ 取模。

**本题有多组测试数据。** 第一行包含一个整数 $T$ $(1\le T\le 10^4)$，表示测试数据组数。 接下来 $T$ 行，每行包含三个整数 $n,k,p$ $(1\le n,k\le 10^6,0\le p\le n)$。 保证所有测试用例的 $n$ 之和不超过 $10^6$。

对于每组测试数据，输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。