题目描述

给定三个整数 $n,k,p$。

考虑所有函数

记 $f^k$ 表示函数 $f$ 的 $k$ 次迭代。若 $x\in\{1,2,\ldots,n\}$ 满足

则称 $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$ 取模后的结果。

样例

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