CF2236F2 Elections in Saransk (hard version)

这是该题目的困难版本。唯一的区别是 $1 \le x \le 5 \cdot 10^5$。 在买完他最喜欢的汽水“Zola Cero”回家的路上，Egor看到在 Saransk 正在进行“最佳数字”职位的选举。 投票站有 $n$ 个人。每个人都带来了一个数字 $a_i$。当第 $i$ 个人进入投票间时，他们会选择一个候选人，该候选人是 $a_i$ 的一个约数。设他们选择的候选人为 $p_i$。 当所有人都投票完后，我们得到了票数数组 $[p_1, p_2, \ldots, p_n]$。 Egor 非常喜欢数字 $x$，并且认为如果 $x \cdot \operatorname{lcm}(p_1, p_2, \ldots, p_n) = p_1 \cdot p_2 \cdot \ldots \cdot p_n$，则本次投票是理想的。请你帮助他计算有多少种不同的 $p$ 数组满足条件，并对 $10^9 + 7$ 取模。 $^{\ast}$ $\operatorname{lcm}$ — [最小公倍数](https://codeforces.com/r/lcm-wiki)。 $^{\dagger}$ 如果存在某个下标 $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$ 取模。

由 ChatGPT 5 翻译