这是问题的简单版本。唯一的区别是 $$$x = 1$$$
在买了他最喜欢的苏打水“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$$$, $$$x = 1$$$) — 投票站的选民人数和 Egor 最喜欢的数字。
每个测试用例的第二行包含 $$$n$$$ 整数: $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 5 \cdot 10^5$$$) — 选民带来的数字。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出以 $$$10^9 + 7$$$ 为模进行投票的方式数,以便生成的投票数组满足条件。
示例
输入复制
44 12 3 1 42 12 46 13 9 1 6 4 57 11 2 3 67 13 8 8
输出复制
844064