#P17614. 01 序列
01 序列
题目描述
有一个长度为 的 序列,它的任意一个长为 的连续子串中都有 个 或 个 。
求可能的序列数。答案很大,请输出其模 的值。
输入格式
输入第一行是数据组数 。
每组数据中,输入一行三个整数:。
输出格式
对于每组数据,输出一个非负整数,为可能的序列数模 的值。
输入输出样例 #1
输入 #1
3
4 3 1
5 3 1
15 7 2
输出 #1
10
16
1586
输入输出样例 #2
输入 #2
5
999999999 14 7
233333333 14 8
333333333 14 9
114514191 14 10
981011451 14 11
输出 #2
278944053
533032251
736989868
589364996
572821890
说明/提示
本题捆绑测试。
对于所有数据,,,,。
详细数据范围如下表:
| Subtask 编号 | 特殊性质 | 分数 | ||
|---|---|---|---|---|
| 无 | ||||
| 无 | ||||