思路1:数论+动态规划

1.切入点:一个很容易感觉到的,对我们很有启发性的事情

​ 找出所有是$k$的倍数的数，假设总共$x$个。那么算下他们的子集个数$2^{x} - 1$

这就是答案了？并不是！ 这不是"$gcd$恰好等于$k$" 的子集个数，而是"$gcd$是$k$的倍数"的子集个数。观察他们的关系，我们可以发现：

"$gcd$是$k$的倍数"的子集个数 = "$gcd$恰好是k"的子集个数 + "$gcd$恰好是$2k$"的子集个数 + .. + "$gcd$恰好是$ck$"的子集个数

题目内容

小红是一个喜欢数学和游戏的年轻人。有一天，他发明了一个新的游戏，可以考验人们的智力和数学知识。

这个游戏的规则很简单：给定一个长度为$n$的整数序列$a$和一个正整数$k$，玩家需要从序列$a$中删掉一些数，使得剩下的数的最大公约数等于$k$。例如，如果序列$a$为$[2,4,6,8]$，$k=2$，则玩家可以删掉$4$和$8$，剩下的数为$[2,6]$，它们的最大公约数是$2$。

小红希望这个游戏能够受到更多人的欢迎，因此他决定把这个游戏发布在他的网站上，并邀请人们来挑战。他相信，这个游戏不仅可以锻炼人们的数学能力，还能帮助人们更好地理解最大公约数的概念。

现在小红想你问有多少种删除的方案。如果答案太大，就把它对 $10^9+7$ 取模。

最大公约数：指两个或多个整数公有约数中最大的一个。

输入描述

第一行输入两个正整数 $n,k$

第二行输入 $n$ 个正整数代表 $a_1,a_2,...,a_n$

$1 \leqslant n, a_i \leqslant 10^5$

输出描述

输出一行整数，代表删除的方案数在$10^9 + 7$ 意义下的取值。

样例

输入

5 5
1 5 2 3 5

输出

3