[Contest #3]子序列子序列子序列...

内存限制：256 MB 时间限制：2000 ms

给定 $n, m$，再给一个含有 $n$ 个正整数的序列 $a_1,a_2, ... ,a_n$，问序列 $a$ 有多少个非空子序列（子序列的定义为能从原序列中去除任意个位置上的元素后得到的序列）是完美的。

一个由正整数组成的序列是完美的，当且仅当它的$\ $每个非空子序列中的整数之和$\ $的和是 $m$ 的倍数。

在本题中，两个子序列只要除去的元素中至少有一个的位置不同，就算不同。观看提示中的样例解释可能可以帮助你更了解题意。

第一行有 $2$ 个由空格分隔的整数 $n,m$。

第二行有 $n$ 个由空格分隔的整数 $a_1,a_2, ... ,a_n$ ，表示给定的序列。

数据满足 $1 \le n \le 5000$，$2 \le m \le 5000$，$0 < a_i < m$。

输出一个数，表示答案对 $1000000007$ ($10^9+7$) 取模后的结果。

样例输入 1

3 8
1 2 3

样例输出 1

样例输入 2

3 2
1 1 1

样例输出 2

样例一中，$n=3$, $m = 8$，给定序列为$[1, 2, 3]$。$[1,2,3]$ 共有 $7$ 个非空子序列：$[1,2,3]$、$[1,2]$、$[1,3]$、$[2,3]$、$[1]$、$[2]$、$[3]$。

其中 $[1,2,3]$ 的 **所有非空子序列的整数之和** 的和为 $(1+2+3)+(1+2)+(1+3)+(2+3)+(1)+(2)+(3) = 24$，是 $m$ 的倍数，所以$[1,2,3]$ 是完美的。

以及 $[1,3]$ 的 **所有非空子序列的整数之和** 的和为 $(1+3)+(1)+(3) = 8$，是 $m$ 的倍数，所以 $[1,3]$ 是完美的。

$[1,2,3]$ 的其他非空子序列都不是完美的，所以答案为 $2$。

样例二中，$n=3$,$m=2$，给定的序列为 $[1,1,1]$。$[1,1,1]$ 也有 $7$ 个子序列：$[1,1,1]$、$3$ 个 $[1,1]$, $3$ 个 $[1]$。

其中 $[1,1,1]$ 和 $[1,1]$ 都是完美的，但 $[1]$ 不是。所以答案为 $4$。