Bitonix' Patrol（CF-217D）

Problem 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).

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 109, 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 109 + 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.

题意：有 n 个点围成一圈，每两个点之间的距离是 m，有 t 个油箱，每个油箱中有一定的油，每行走距离 1 消耗 1 单位的油，现在某人从某点开始出发，连接 x 个油箱并选择顺时针或逆时针行走，只有当再次到达这个点才算完成巡逻，现在要摧毁一些油箱，使得无法完成巡逻，问最多有多少种摧毁方案，最后的结果模 1E9+7

思路：

首先考虑 t 个油箱 ai 与距离 m 的关系，由于只有当油耗尽后才能停止，且只能选择顺时针和逆时针，因此可以考虑 ai 模 m 的余数，同余的两个数字不能同时出现，此时可将这两个数字一个标记为 1，一个标记为 -1，其他数字标记为 0

假设 x 与 m 不能同时出现，那么对于超过 m/2 的余数 x，只用考虑 m-x 即可，由于 m 最大到 120，因此余数集的长度降到 60，即问题的规模降到了 2^60，假设当前存在一个集合维护了不能出现的数字，那么当前可以取的余数不能在这个集合中，使用 bitset<60> 来存储当前不能存的数字，然后进行 dfs

在 dfs 的过程中，假设当前取的数字为 k，bitset 为 bs，那么 bs 中第 k 位于第 m-k 位不能是 1，取 k 后，原先不能取的数字集合、原先不能取的数字集中每个数字 - k 得到的集合、原先不能取的数字集中每个数字 + k 得到的集合的并集，变为新的不能取的集合

由于 bitset 没有循环移位，所以可将循环移位进行拆解，有：

• 左移 k 位时：先左移 k 位，再右移 m-k 位，最后两者取或，即：（bs<<k）|（bs>>(m-k)）
• 右移 k 位时：先右移 k 位，再左移 m-k 位，最后两者取或，即：（bs>>k）|（bs<<(m-k)）

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 125+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

int n,m,k;
int bucket[N];
LL res;
bitset<N> left(bitset<N> &x,int val,int len) {//循环左移
    return (x<<val)|(x>>(len-val));
}
bitset<N> right(bitset<N> &x,int val,int len) {//循环右移
    return (x>>val)|(x<<(len-val));
}
void dfs(bitset<N> bs,int cnt,LL pos) {//已经拿了cnt个，从体积为pos开始选择是否拿
    res=(res+pos)%MOD;
    for(int i=cnt;i<=m/2;i++) {
        if(bucket[i] && !bs[i] && !bs[m-i]) {
            LL newPos=pos*bucket[i]%MOD;
            bitset<N> newBs=bs|left(bs,i,m)|right(bs,i,m);
            dfs(newBs,i+1,newPos);
        }
    }

}
int main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<k;i++) {
        int x,nx;
        scanf("%d",&x);
        x%=m;//顺时针
        nx=m-x;//逆时针
        int minn=min(x,nx);
        bucket[minn]++;
    }
    bitset<N> bs=1;
    dfs(bs,0,1);
    res%=MOD;
    printf("%d\n",res);
    return 0;
}