这是问题的困难版本。唯一的区别是 $$$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$$$ 为模进行投票的方式数,以便生成的投票数组满足条件。
示例
输入复制
52 22 41 557 42 4 8 13 111 6 73 10001 2 33 34 8 10
输出复制
2036000