题目描述

给定 $n$ 个整数 $a_1,a_2,\cdots, a_n$。从下标 $1$ 到 $n$中，能挑选出多少种非空的下标子集，使得对应数字之和是 $k$ 的倍数。

输入格式

第一行：两个整数 $n$ 与 $k$； 第二行：$n$ 个整数 $a_1,\dots,a_n$。

输出格式

单个整数：表示和为 $k$ 倍数的子集数量。由于答案可能比较大，输出答案对 $10^9+7$ 取模的余数。

4 3
3 1 2 4

5

样例解释 1

{3},{1,2},{2,4},{3,1,2},{3,2,4}满足子集和为3的倍数

3 5
2 3 3

2

样例解释 2

两个能够整除5的子集均为{2,3}

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 20$；
• 对于 $60\%$ 的数据，$1\leq n\leq 100，1 \leq k \leq 10^4，1 \leq a_i \leq 10^4$；
• 对于 $100\%$ 的数据，$1\leq n\leq 1000，1 \leq k\leq 10^5，1 \leq a_i \leq 10^9$。