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

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

题目描述

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

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

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

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

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

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

请你帮他求出方案数对 10^9 + 7 取模的结果。

输入格式

第一行三个整数表示 n , m q

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

输出格式

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

样例

样例1

2 3 3
1
5
6
9
6
1

样例2

5 3 4
2
4
6
8
225
2001
6014
6939

样例1说明

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

x = 1 ,小 Y 可以选择在第一天或第二天取出 1 对重粒子对,方案数为 3 + 6 = 9

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

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

数据范围与提示

测试点 n m n\times m q
1,2 \le 2 \le 10 \le 20 \le10
3,4 \le 10 \le 100 \le 10
5,6 \le 10^5 =1 \le 1\times10^5 \le 10^5
7,8 =2 \le 2\times10^5
9,10,11,12 =3 \le 3\times10^5
13,14,15,16 \le 10 \le 5\times10^5 \le 10
17,18 \le 10^5
19,20 \le 10^6 \le 10^6

对于所有数据满足 n\le10^6,m\le10, x\le n\times m\le3\times 10^6, q\le10^6