该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个整数 $a_1,a_2,⋯,a_n$。

从下标 $1$ 到 下标 $n$ 中，挑出一些下标，构成一个子集。

请统计有多少种方法，可以使得这些下标对应的数字之和是一个给定整数 $k$ 的倍数，且下标子集不空。

由于答案可能比较大，输出答案对 $10^9+7$ 取模的余数。

输入格式

第一行：两个整数 $n$ 与 $k$；

第二行：$n$ 个整数 $a_1,…,a_n$。

输出格式

单个整数：表示答案。

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≤n≤20$；

对于 $60$% 的数据，$1≤n≤100，1≤k≤10^4，1≤a_i≤10^4$；

对于 $100$% 的数据，$1≤n≤1000，1≤k≤10^5，1≤a_i≤10^9$。