普通链是一个由连续（至少两个）顶点组成的图。每两个相邻顶点之间由一条边连接。$k$ 阶 Chiaki 链与普通链略有不同。在主链的 $k$ 个不同顶点上延伸出 $k$ 条不同长度的子链。在每条子链的另一端，分别连接着一个长度为 $3, 4, \dots, k+2$ 的简单环。$k$ 阶 Chiaki 链中没有多余的顶点或边。

注意，主链和子链应至少包含两个顶点。

下图对应一个具有 20 个顶点和 22 条边的 3 阶 Chiaki 链：

给定 $n, m$ 和 $k$，Chiaki 想知道具有 $n$ 个顶点和 $m$ 条边的带标号 $k$ 阶 Chiaki 链的数量。由于这个数字可能非常大，你只需要计算它对 $10^9 + 7$ 取模的结果。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m, k \le 10^6$)，分别表示图中的顶点数、边数以及 Chiaki 链的阶数。

输出格式

对于每组测试数据，输出一个整数表示答案。

样例

输入 1

4
1 1 1
3 3 1
4 4 1
5 5 1

输出 1

0
0
0
60