题目描述

在 Wartshog 魔法学校，新生要按固定顺序被分到三个学院：Andorgryff、Bufflehuff 和 Clawenrave。

三个学院分别有恰好 $A,B,C$ 个名额，共有 $A+B+C$ 名新生。分院帽还必须遵守下面的规则：

任意两名相邻的新生不能被分到同一个学院。

求满足条件的分配序列数量。若至少有一名学生所属学院不同，则认为两个分配方案不同。答案对 $10^9+7$ 取模。

输入格式

第一行包含整数 $T$，表示测试用例数量。

接下来 $T$ 行，每行包含三个整数 $A,B,C$。

输出格式

对每个测试用例输出一行，表示合法分配方案数对 $10^9+7$ 取模后的结果。

数据范围

• $1\le T\le 20$；
• $0\le A,B,C\le 100000$；
• $A+B+C\ge 1$。

子任务

样例

输入
5
2 3 0
2 2 1
4 1 1
100 100 100
100000 100000 1

输出
1
12
0
105481704
600000

样例说明

第一组中唯一的合法序列为 BABAB。

第二组共有 12 种方案：ABABC、ABACB、ABCAB、ABCBA、ACBAB、BABAC、BABCA、BACAB、BACBA、BCABA、CABAB、CBABA。

第三组中无论如何排列都会出现相邻的两个 A，因此答案为 0。