题目描述

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

输入格式

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

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

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

输出格式

一个数，为结果。

样例

3
1 2 3
2

4