跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0210. #2220. 「HEOI2014」平衡

    ID: 216 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>待分类整理状态难度待定难度共享题库LibreOJ中文题面题目来源题面语言

#2220. 「HEOI2014」平衡

题目描述

下课了,露露、花花和萱萱在课桌上用正三棱柱教具和尺子摆起了一个「跷跷板」。

这个「跷跷板」的结构是这样的:底部是一个侧面平行于地平面的正三棱柱教具,上面摆着一个尺子,尺子上摆着若干个相同的橡皮。尺子有 条等距的刻度线,第 条刻度线恰好在尺子的中心,且与正三棱柱的不在课桌上的棱完全重合。

露露发现这个「跷跷板」是不平衡的(尺子不平行于地平面)。于是,她又在尺子上放了几个橡皮,并移动了一些橡皮的位置,使得尺子的 条刻度线上都恰有一块相同质量的橡皮。「跷跷板」平衡了,露露感到很高兴。

花花觉得这样太没有意思,于是从尺子上随意拿走了 个橡皮。令她惊讶的事情发生了: 尺子依然保持着平衡!

萱萱是一个善于思考的孩子,她当然不对尺子依然保持平衡感到吃惊,因为这只是一个偶然的事件罢了。令她感兴趣的是,花花有多少种拿走 个橡皮的方法,使得尺子依然保持平衡?

当然,为了简化问题,她不得不做一些牺牲——假设所有橡皮都是拥有相同质量的质点。但即使是这样,她也没能计算出这个数目。放学后,她把这个问题交给了她的哥哥/ 姐姐——Hibarigasaki 学园学生会会长,也就是你。当然,由于这个问题的答案也许会过于庞大,你只需要告诉她答案 modp 的值。

输入格式

第一行,一个正整数,表示数据组数 (萱萱向你询问的次数)。
接下来 行,每行三个正整数 。

输出格式

共 行,每行一个正整数,代表你得出的对应问题的答案。

样例

样例输入

10 
6 5 10000 
4 1 10000 
9 6 10000 
4 6 10000 
5 1 10000 
8318 10 9973 
9862 9 9973 
8234 9 9973 
9424 9 9973 
9324 9 9973

样例输出

73
1
920
8
1
4421
2565
0
446
2549

数据范围与提示

对于所有的数据,,且 。


题目来源:fps-loj-small-pics.zip;FPS 共享题包,题包内第 99 题。保留原作者与原赛事署名。