Clarke and problem

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

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 $a_1, a_2, ..., a_n$ 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 $10^9+7$

Input

The first line contains one integer $T(1 \le T \le 10)$ - the number of test cases.
$T$ test cases follow.
The first line contains two positive integers $n, p(1 \le n, p \le 1000)$
The second line contains $n$ integers $a_1, a_2, ... a_n(|a_i| \le 10^9$).

Output

For each testcase print a integer, the answer.

Sample Input

1 2 3 1 2

Sample Output

2 Hint: 2 choice: choose none and choose all.

Hint

hujie

Source

BestCoder Round #56 (div.2)

提交代码