#525. 「多校联考 Round 3」粒子加速器

内存限制:256 MiB 时间限制:1000 ms 输入文件:accelerator.in 输出文件:accelerator.out
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 Y 有一个来自未来的粒子加速器。

这个加速器每天都能将 对电子 和正电子 湮灭,产生 对重粒子对 ,可以认为第 天时加速器中有 对重粒子对。根据动量守恒定律和能量守恒定律,不存在单一的 。我们认为每对重粒子对都是不同的。

这个粒子加速器还有一个人为规定的参数 ,当加速器中的重粒子个数大于等于 时,小 Y 可以从加速器中取出 对重粒子对进行原子核物理学的实验。

由于小 Y 没有为粒子加速器供能所需要的等离子体发电机,这个加速器只能持续工作 天。

小 Y 想求出对于给定的参数 ,加速器会有多少种不同的选出重粒子对的方法。两种方案不同,当且仅当取出重粒子对的天数不同或者取出的重粒子对的集合不同。

他来求助学习 OI 的你,你决定帮助小 Y 完成他的物理实验。

请你帮他求出方案数对 取模的结果。

输入格式

第一行三个整数表示 ,

之后行,每行一个整数,表示每次询问的

输出格式

行,表示每次询问的答案。

样例

样例1

2 3 3
1
5
6
9
6
1

样例2

5 3 4
2
4
6
8
225
2001
6014
6939

样例1说明

第一天加速器中有 对重粒子,第二天加速器中有 对重粒子。

,小 Y 可以选择在第一天或第二天取出 对重粒子对,方案数为

,由于在第一天加速器中没有足够的重粒子对,因此只能在第二天取,方案数为

,只能在第二天将 对重粒子对全部取走,方案数为

数据范围与提示

测试点

对于所有数据满足