← 返回题目列表

Codeforces · 217/D

D. Bitonix 巡逻

中文机器翻译题面 查看原题

Byteland 正在尝试向 Bit-X 星球发送太空任务。他们的任务很复杂,因为 Bit-X 太空部队的领导人 Bitonix 上尉定期在行星轨道上巡逻。

Bit-X 周围有 n 个站,从 1 到 n 顺时针编号。这些站均匀地放置在圆形轨道上,因此编号 i 和 i + 1 (1 ≤ i < n) 的站以及编号 1 和 n 的站是相邻的。每对相邻站点之间的距离等于 m 空间英里。为了进行巡逻,比托尼克斯上尉在其中一个空间站跳入他的火箭,绕圈飞行,飞行距离至少一英里,然后到达某个空间站(可能是起始空间站)。

Bitonix 的火箭通过燃烧燃料箱来移动。 Bitonix 连接 x 升燃料箱并选择方向(顺时针或逆时针)后,火箭将沿着所选方向的圆形轨道精确飞行 x 空间英里。请注意,火箭没有刹车;在耗尽燃料箱之前火箭不可能停止。

例如,假设 n = 3 且 m = 60,且 Bitonix 的油箱容量为 10、60、90 和 100 升。如果Bitonix从1号站出发,用100升油箱顺时针走,再用90升油箱顺时针走,再用10升油箱逆时针走,他就会回到1号站。这样就构成了一次有效的巡逻。请注意,Bitonix 不必使用所有可用的油箱。在本例中,Bitonix 的另一个有效选择是简单地使用 60 升油箱飞往 2 号或 3 号车站。

然而,如果n等于3,m等于60,并且Bitonix可用的唯一油箱是一个10升油箱和一个100升油箱,他将无法完成有效的巡逻(他将无法准确地在车站完成任何巡逻)。

Byteland 航天局想要摧毁 Bitonix 船长的一些油箱,使他无法完成任何有效的巡逻。找出该机构可以摧毁多少个不同的坦克子集,以阻止 Bitonix 队长完成巡逻,并输出模 1000000007 (109 + 7) 的答案。

输入

输入的第一行包含三个整数 n (2 ≤ n ≤ 1000) — 车站数量,m (1 ≤ m ≤ 120) — 相邻车站之间的距离,以及 t (1 ≤ t ≤ 10000) — Captain Bitonix 拥有的油箱数量。

输入的第二行包含 t 个以空格分隔的 1 到 109 之间的整数(含 1 和 109)——Bitonix 油箱的容量。

输出

输出一个数字 — Bytelandian 航天局为了阻止 Bitonix 上尉完成巡逻而可以摧毁的不同坦克子集的数量,模 109 + 7。

示例

输入 #1

7 6 5
5 4 12 6 5

输出 #1

6

输入 #2

3 60 2
10 100

输出 #2

4

注意

所有油箱都是不同的,即使其中一些具有相同的容量。