3738: Bitonix' Patrol
Description
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).
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.
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.
7 6 5
5 4 12 6 5
6
3 60 2
10 100
4
All the fuel tanks are distinct, even if some of them have the same capacity.