Clarke and problem

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$

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

For each testcase print a integer, the answer.

1
2 3
1 2

2

Hint:
2 choice: choose none and choose all.

BestCoder Round #56 (div.2)