Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Bitonix' Patrol

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputByteland 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 (10^{9} + 7).

Input

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

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.

Examples

Input

7 6 5

5 4 12 6 5

Output

6

Input

3 60 2

10 100

Output

4

Note

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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2018 02:52:55 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|