← 返回题目列表

Codeforces · 2236/F2

F2. 萨兰斯克选举(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是 $$$1 \le x \le 5 \cdot 10^5$$$.

在买了他最喜欢的苏打水“Zola Cero”回家的路上,叶戈尔看到萨兰斯克正在举行“最佳号码”职位的选举。

投票站有 $$$n$$$ 人。每个人都带了一个号码$$$a_i$$$。当第 $$$i$$$ 人进入投票站时,他们会选择一位候选人,该候选人是 除数 号码 $$$a_i$$$ 的 。令所选候选人为$$$p_i$$$。

每个人都投票后,我们得到一系列选票 $$$[p_1, p_2, \ldots, p_n]$$$。

Egor 非常喜欢 $$$x$$$ 这个数字,并认为如果 $$$x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$$$$^{\text{*}}$$$ = $$$p_1 \cdot p_2 \cdot \ldots \cdot p_n$$$ 是理想的投票。帮助他找到理想的不同 $$$^{\text{†}}$$$ 数组 $$$p$$$ 模 $$$10^9 + 7$$$ 的数量。

$$$^{\text{*}}$$$$$$lcm$$$ — 最小公倍数。

$$$^{\text{†}}$$$考虑两个投票数组 不同 如果存在索引 $$$i$$$,其中两个数组具有不同的元素。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq x \leq 5 \cdot 10^5$$$) — 投票站的选民人数和 Egor 最喜欢的数字。

每个测试用例的第二行包含 $$$n$$$ 整数: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$) — 选民带来的数字。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出以 $$$10^9 + 7$$$ 为模进行投票的方式数,以便生成的投票数组满足条件。

示例

输入
复制

5
2 2
2 4
1 5
5
7 4
2 4 8 13 111 6 7
3 1000
1 2 3
3 3
4 8 10

输出
复制

2
0
360
0
0