3734. 组合游戏

单点时限: 1.0 sec

内存限制: 256 MB

“由于天气原因,今天航路会一路颠簸,所有机上的服务将会暂停。”

空乘人员没有了服务的工作,在飞行途中就没有固定的工作安排了。

空乘人员在上一个字母游戏中落败,但她并不服气。她觉得是 Cuber QQ 出了自己擅长的题,她才无法取胜。

于是这一次游戏,由空乘人员来决定游戏。

空乘人员会给出三个数

她认为一个集合如果是完美的,必须要满足以下条件:

  • 当且仅当这个集合是集合 的子集;

  • 这个集合包含 个不同的奇数和 个不同的偶数;

  • 集合中任意挑选两个数,他们都是不相邻的(如果两个数是相邻的,当且仅当他们差的绝对值为 或者他们分别是 )。

现在空乘人员询问 Cuber QQ 能不能计算出这样符合要求的完美的集合总数量。

由于数量可能会很大,空乘人员为了不为难 Cuber QQ ,她允许 Cuber QQ 给出的答案对 取模。

输入格式

输入第一行包含一个整数 ,表示数据组数。

接下来的 行,每行包含三个整数

输出格式

对于每一组数据,输出一行包含一个整数,表示答案。

样例

Input
1
1 1 0
Output
1
Input
2
3 2 0
2 2 0
Output
3
1
Input
2
4 2 1
4 3 1
Output
4
0

14 人解决,33 人已尝试。

15 份提交通过,共有 110 份提交。

6.8 EMB 奖励。

创建: 1 周,3 天前.

修改: 1 周,2 天前.

最后提交: 10 小时前.

来源: N/A

题目标签