分数游戏（简单版）

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

Alice 与 Bob 进行 $n$ 回合游戏，分数初始为零。每回合 Alice 先选一个 $[0,k]$ 内的实数，随后 Bob 在看到该数后选择把它加到或从分数中减去。Alice 在下一回合开始前知道 Bob 上一回合的选择。Bob 必须在至少 $m$ 个回合选择加法。

Alice 最大化最终分数，Bob 最小化最终分数。求双方采用最优策略时的最终分数。

答案是一个有理数。设其最简形式为 $p/q$，输出 $p q^{-1}\bmod(10^9+7)$。

输入格式

第一行包含测试组数 $t$。随后每组一行包含 $n,m,k$。

输出格式

每组输出一个整数答案。

样例输入 1

7
3 3 2
2 1 10
6 3 10
6 4 10
100 1 1
4 4 0
69 4 20

样例输出 1

6
5
375000012
500000026
958557139
0
49735962

数据范围

• $1\le t\le1000$；
• $1\le m\le n\le2000$；
• $0\le k<10^9+7$；
• 所有测试组的 $n$ 之和不超过 $2000$。