容斥

#include <bits/stdc++.h>

#define ZhangHaoYang using
#define Jvav namespace
#define Master std

题目内容

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

这个游戏的规则很简单：给定一个长度为$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