题目描述

给一个长度为$n$的序列$a$，你需要求出它有多少非空子序列的乘积是$m$的倍数。你需要求出这个数对$10^9+7$取模的结果。

一个长度为$n$的序列的非空子序列是指从其中删除$0\leq k\leq n-1$个数得到的序列。两个子序列被认为是不同的当且仅当得到这两个子序列删除的元素至少有一个在原序列中位置不同。例如$\{1,2,5\}$的非空子序列有$\{1\},${2},$\{5\},\{1,2\},\{2,5\},\{1,5\},\{1,2,5\}$；$\{1,1\}$的非空子序列有$\{1\},\{1\},\{1,1\}$。

输入格式

第一行两个整数$n,m$。

第二行$n$个整数，代表序列。

输出格式

输出一个整数， 代表答案。

输入样例1

3 6
2 3 6

输出样例1

5

输入样例2

5 100
1 2 3 4 5

输出样例2

0

对于第一组样例，符合条件的子序列有$\{2,3\},\{2,6\},\{3,6\},\{6\},\{2,3,6\}$

数据范围

对于$30\%$的数据，$n,m\leq 10,a_i\leq 5$

对于$60\%$的数据，$n,m\leq 1000,a_i\leq 1000$

对于另外$20\%$的数据，保证$m$是质数

对于所有数据，$1\leq n,m\leq 10^5,1\leq a_i\leq 10^5$

点此下载