Coco 经营着一家巧克力工厂。该工厂的机器生产 $3 \times N$ 大小的矩形巧克力块。Coco 计划将这块巧克力分割成 $\lfloor \frac{3N}{2} \rfloor$ 个大小为 $1 \times 2$ 或 $2 \times 1$ 的巧克力块进行销售。不知为何，$N$ 总是奇数，因此 Coco 决定选择一个 $1 \times 1$ 的小块吃掉，然后将剩下的部分分割销售。给定 $N$ 的值以及 Coco 吃掉的小块的位置（第 $R$ 行第 $C$ 列），请计算将剩下的巧克力块分割的方法数。

输入格式

第一行包含测试用例的数量 $T$。对于每个测试用例，在一行中给出 $N$、$R$ 和 $C$ 的值。

输出格式

在每行中输出每个测试用例的答案。由于答案可能非常大，请输出模 $10^9+7$ 后的余数。

样例

样例输入 1

3
5 1 1
5 2 2
5 1 2

样例输出 1

15
8
0

说明

$1 \le T \le 100000$，$1 \le N \le 100000$，$1 \le R \le 3$，$1 \le C \le N$，$N$ 是奇数。