题目描述

输入 $n$，然后输入 $n$ 个数，再输入 $m$ ,请问从这 $n$ 个数中任意选取若干个数(每个数的大小不超过 $10^9$ )相加（包括一个数都不取），有多少种情况，相加后的和能被 $m$ 整除？

由于满足条件的方案可能很多，输出结果对 $10000007$ 取模。

输入格式

第一行，一个整数 $n$ ($1 \le n \le 1000$ )

第二行，$n$ 个用空格隔开的数 $a_i$ ( $1 \le a_i \le 10^9$ )

第三行，一个整数，$m$ ($1 \le m \le 30000$ )

输出格式

一个数，为方案数 % $10000007$ 。

样例

3
1 2 3
2

4