Clarke is a patient with multiple personality disorder. One day, Clarke turned into a student and read a book.
Suddenly, a difficult problem appears: 
You are given a sequence of number  a1,a2,...,an and a number  p. Count the number of the way to choose some of number(choose none of them is also a solution) from the sequence that sum of the numbers is a multiple of  p( 0 is also count as a multiple of  p). Since the answer is very large, you only need to output the answer modulo  109+7

The first line contains one integer  T(1≤T≤10) - the number of test cases. 
T test cases follow. 
The first line contains two positive integers  n,p(1≤n,p≤1000) 
The second line contains  n integers  a1,a2,...an(|ai|≤109).

For each testcase print a integer, the answer.

BestCoder Round #56 (div.2)

翻译：

克拉克是一名人格分裂患者。某一天，克拉克分裂成了一个学生，在做题。 
突然一道难题难到了克拉克，这道题是这样的：  
给你$n$个数，要求选一些数（可以不选），把它们加起来，使得和恰好是$p$的倍数（$0$也是$p$的倍数），求方案数。  
对于$n$很小的时候，克拉克是能轻易找到的。然而对于$n$很大的时候，克拉克没有办法了，所以来求助于你。  

第一行一个整数$T(1\le T\le 10)$，表示数据的组数。  
每组数据第一行是两个正整数$n,p(1\le n,p\le 1000)$。  
接下来的一行有$n$个整数a_i(|a_i| \le 10^9)a​i​​(∣a​i​​∣≤10​9​​)，表示第$i$个数。

对于每组数据，输出一个整数，表示问题的方案数，由于答案很大，所以求出对10^9+710​9​​+7的答案即可。  

1
2 3
1 2

2

解题思路:

官方提示：

Clarke and problem

设$d(i,j)$表示前$i$个数，模$p$为$j$的方案数，则容易得到d(0, 0)=1, d(i, j)=d(i-1, j)+\sum_{j=0}^{p-1} d(i-1, (j-a[i]) \ mod \ p)d(0,0)=1,d(i,j)=d(i−1,j)+∑​j=0​p−1​​d(i−1,(j−a[i]) mod p)，很多人没1a是因为没注意|a_i| \le 10^9∣a​i​​∣≤10​9​​

个人认为这其实就是一个dp的题，因为以前做过这样类似的，所以1 A

哈哈，上代码：

/**
2015 - 09 - 20 晚上

Author: ITAK

Motto:

今日的我要超越昨日的我，明日的我要胜过今日的我，
以创作出更好的代码为目标，不断地超越自己。
**/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long LL;
const int maxn = 1005;
const int mod = 1e9+7;
const double eps = 1e-7;
int arr[maxn], dp[maxn], fac[maxn];
///arr数组保证每个值都是k的余数( <k 的)
int main()
{
    int T, m, p, k;
    cin>>T;
    while(T--)
    {
        memset(dp, 0, sizeof(dp));
        memset(fac, 0, sizeof(fac));
        dp[0] = 1;
        cin>>m>>p;
        for(int i=0; i<m; i++)
        {
            cin>>k;
            k %= p;
            if(k < 0)
                k += p;
            arr[i] = k;
        }
        for(int i=0; i<m; i++)
        {
            for(int j=0; j<p; j++)
                fac[j] = dp[j];///这句很重要啊
            for(int j=0; j<p; j++)
            {
                k = (j+arr[i])%p;
                fac[k] += dp[j];
            }
            for(int j=0; j<p; j++)
                dp[j] = fac[j]%mod;
        }
        cout<<dp[0]<<endl;
    }
    return 0;
}