#1009. I. 人才吸纳,多方交流合作

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

你的团队创立至今,已成为全国最好的量化投资研发和技术团队之一。团队成员多数毕业于国内外知名高校,专业覆盖了经济、金融、统计、数学、物理、计算机等,拥有强大的学术和科研能力。编写的金融二级市场的回测平台在国内处于领先地位,且公司与国内众多顶尖教育机构展开全面合作,包括你的母校xjtu、以及清华、北大、中科大、哥伦比亚大学、麻省理工等国内外著名高校。

为了把更多的优秀人才凝聚在一起,你们设计了坐标游戏:

有一个无限的二维坐标平面一开始cyy和csf的坐标均为,然后游戏会进行轮,每轮有两步。

第一步:cyy和csf的坐标均,然后法官ddd会钦定其中一人,这个人的坐标,另一个人的坐标不变。

第二步:cyy和csf的坐标均,然后法官ddd会钦定其中一人,这个人的坐标,另一个人的坐标不变。

这样进行轮后,csf和cyy会在坐标系上留下两条行走的轨迹。设cyy到达过的最大的y坐标,v为csf到达过的最大的y坐标

求有多少种可能的行走轨迹使得,答案对取模。

输入格式

一行一个整数,代表数据组数。

接下来组数据,对于每组数据:

一行三个正整数:

输出格式

行,每行一个整数,表示答案。

样例

样例输入 样例输出
2
2 3 100
100 1 100
56
4

数据范围与提示

保证的数据不多于二十五组,的数据不多于四组,的数据不多于一组。