给一个长度为n的序列a，你需要求出它有多少非空子序列的乘积是m的倍数。你需要求出这个数对10^9+7取模的结果。
一个长度为n的序列的非空子序列是指从其中删除0<=k<=n-1个数得到的序列。两个子序列被认为是不同的当且仅当得到这两个子序列删除的元素至少有一个在原序列中位置不同。例如{1,2,5}的非空子序列有{1},{2},{5},{1,2},{2,5},{1,5},{1,2,5}; {1,1}的非空子序列有{1},{1},{1,1}。
给一个长度为n的序列a，你需要求出它有多少非空子序列的乘积是m的倍数。你需要求出这个数对10^9+7取模的结果。
一个长度为n的序列的非空子序列是指从其中删除0<=k<=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个整数，代表序列。
输出一个整数， 代表答案。
3 6 2 3 6
5
样例2输入
5 100
1 2 3 4 5
样例2输出
0
样例1说明：
符合条件的子序列有{6},{2,3},{2,6},{3,6},{2,3,6}。
数据范围：
对于30%的数据，n,m<=10,ai<=5；
对于60%的数据，n,m<=1000,ai<=1000；
对于另外20%的数据，保证m是质数；
对于所有数据，1<=n,m<=10^5,1<=ai<=10^5。