Bitonix' Patrol

题意翻译

一个环上有$n(2\le n\le 1000)$个点，每个点间距为$m(1\le m\le 120)$，现在你有$t(1\le t\le 10000)$个油箱，每个油箱可以让你走$a_i(1\le a_i\le 10^9)$的距离，你可以选择顺时针走或逆时针走，但是不能中途折返，求取走任意数量的油箱后你无法从一个点出发到达任意一个点的方案数，答案对$10^9+7$取模

题目描述

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&lt;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 $ $ (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 $ 10^{9} $ , inclusive — the volumes of Bitonix' fuel tanks.

输出格式

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 $ 10^{9}+7 $ .

输入输出样例

输入样例 #1

7 6 5
5 4 12 6 5

输出样例 #1

6

输入样例 #2

3 60 2
10 100

输出样例 #2

4

说明

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