CF217D.Bitonix' Patrol

Byteland is trying to send a space mission onto the Bit-X planet. Their task is complicated by the fact that the orbit of the planet is regularly patrolled by Captain Bitonix, the leader of the space forces of Bit-X.

There are n stations around Bit-X numbered clockwise from 1 to n. The stations are evenly placed on a circular orbit, so the stations number i and i + 1 (1 ≤ i < n), and the stations number 1 and n, are neighboring. The distance between every pair of adjacent stations is equal to m space miles. To go on a patrol, Captain Bitonix jumps in his rocket at one of the stations and flies in a circle, covering a distance of at least one space mile, before finishing in some (perhaps the starting) station.

Bitonix' rocket moves by burning fuel tanks. After Bitonix attaches an x-liter fuel tank and chooses the direction (clockwise or counter-clockwise), the rocket flies exactly x space miles along a circular orbit in the chosen direction. Note that the rocket has no brakes; it is not possible for the rocket to stop before depleting a fuel tank.

For example, assume that n = 3 and m = 60 and Bitonix has fuel tanks with volumes of 10, 60, 90 and 100 liters. If Bitonix starts from station 1, uses the 100-liter fuel tank to go clockwise, then uses the 90-liter fuel tank to go clockwise, and then uses the 10-liter fuel tank to go counterclockwise, he will finish back at station 1. This constitutes a valid patrol. Note that Bitonix does not have to use all available fuel tanks. Another valid option for Bitonix in this example would be to simply use the 60-liter fuel tank to fly to either station 2 or 3.

However, if n was equal to 3, m was equal to 60 and the only fuel tanks available to Bitonix were one 10-liter tank and one 100-liter tank, he would have no way of completing a valid patrol (he wouldn't be able to finish any patrol exactly at the station).

The Byteland space agency wants to destroy some of Captain Bitonix' fuel tanks so that he cannot to complete any valid patrol. Find how many different subsets of the tanks the agency can destroy to prevent Captain Bitonix from completing a patrol and output the answer modulo 1000000007 (109 + 7).

Byteland 正试图向 Bit-X 行星发射一次太空任务。然而，这一任务因 Bit-X 星球轨道上持续进行的巡逻而变得复杂——巡逻由 Bit-X 太空部队指挥官 Captain Bitonix 负责。

Bit-X 周围共有 $ n $ 座空间站，按顺时针方向编号为 $ 1 $ 至 $ n $。这些空间站均匀分布在一条圆形轨道上，因此空间站 $ i $ 与 $ i+1 $（其中 $ 1 \le i < n $）互为邻站，且空间站 $ 1 $ 与 $ n $ 也互为邻站。任意两个相邻空间站之间的距离均为 $ m $ 个太空英里。为执行一次巡逻任务，Captain Bitonix 会在某一座空间站登上火箭，沿圆周飞行至少一英里后，在某一（可能是出发）空间站结束飞行。

Bitonix 的火箭通过燃烧燃料罐推进。当他安装一个容量为 $ x $ 升的燃料罐并选定飞行方向（顺时针或逆时针）后，火箭将严格沿所选方向在圆形轨道上飞行恰好 $ x $ 个太空英里。注意：火箭没有制动装置；在耗尽当前燃料罐之前无法中途停止。

例如，假设 $ n = 3 $、$ m = 60 $，且 Bitonix 拥有容量分别为 $ 10 $、$ 60 $、$ 90 $ 和 $ 100 $ 升的燃料罐。若 Bitonix 从空间站 $ 1 $ 出发，先使用 $ 100 $ 升燃料罐顺时针飞行，再使用 $ 90 $ 升燃料罐顺时针飞行，最后使用 $ 10 $ 升燃料罐逆时针飞行，则他将恰好返回空间站 $ 1 $。这构成一次合法的巡逻。注意：Bitonix 并非必须使用所有可用的燃料罐。在此例中，另一合法方案是仅使用 $ 60 $ 升燃料罐飞往空间站 $ 2 $ 或 $ 3 $。

然而，若 $ n = 3 $、$ m = 60 $，且 Bitonix 手中仅有 $ 10 $ 升和 $ 100 $ 升两个燃料罐，则他将无法完成任何合法巡逻（即无法使飞行终点恰好落在某一座空间站上）。

Byteland 太空署希望摧毁 Captain Bitonix 的一部分燃料罐，使得他再也无法完成任何合法巡逻。请计算有多少种不同的燃料罐子集可被摧毁，从而达成该目标，并将答案对 $ 1000000007 $（即 $ 10^9 + 7 $）取模后输出。

The first line of the input contains three integers n (2 ≤ n ≤ 1000) — the number of stations, m (1 ≤ m ≤ 120) — the distance between adjacent stations, and t (1 ≤ t ≤ 10000) — the number of fuel tanks owned by Captain Bitonix.

The second line of the input contains t space-separated integers between 1 and 109, inclusive — the volumes of Bitonix' fuel tanks.

输入的第一行包含三个整数 $n$（$2 \leq n \leq 1000$）—— 车站的数量，$m$（$1 \leq m \leq 120$）—— 相邻车站之间的距离，以及 $t$（$1 \leq t \leq 10000$）—— Captain Bitonix 拥有的油箱数量。

输入的第二行包含 $t$ 个用空格分隔的整数，每个整数在 $1$ 到 $10^9$ 之间（含端点）—— Bitonix 各油箱的容积。

Output a single number — the number of distinct subsets of tanks that the Bytelandian space agency can destroy in order to prevent Captain Bitonix from completing a patrol, modulo 109 + 7.

输出一个整数——Byteland 航天局能够摧毁的、以阻止 Bitonix 船长完成巡逻的不同油罐子集的数量，结果对 $10^9 + 7$ 取模。

All the fuel tanks are distinct, even if some of them have the same capacity.

所有油箱均互不相同，即使其中某些油箱的容量相同。