CF2236F1.Elections in Saransk (easy version)

This is the easy version of the problem. The only difference is that $x = 1$

On the way home after buying his favorite soda "Zola Cero", Egor saw that elections for the position of "Best Number" are taking place in Saransk.

There are $n$ people at the polling station. Each person brought a number $a_i$. When the $i$-th person enters the voting booth, they choose a candidate that is a divisor of the number $a_i$. Let the chosen candidate be $p_i$.

After everyone has voted, we get an array of votes $[p_1, p_2, \ldots, p_n]$.

Egor really likes the number $x$ and considers the voting ideal if $x \cdot {lcm}(p_1, p_2, \ldots, p_n)$$^{\text{∗}}$ = $p_1 \cdot p_2 \cdot \ldots \cdot p_n$. Help him find the number of different$^{\text{†}}$ arrays $p$ modulo $10^9 + 7$ that are ideal.

$^{\text{∗}}$$lcm$ — least common multiple.

$^{\text{†}}$Two arrays of votes are considered different if there exists an index $i$ where the two arrays have different elements.

这是该问题的简单版本。唯一的区别是 $x = 1$。

在买完他最喜欢的汽水“Zola Cero”回家的路上，Egor 发现萨兰斯克正在举行“最佳数字”职位的选举。

投票站共有 $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$ 时，他认为此次投票是理想的。请帮助他计算模 $10^9 + 7$ 意义下，有多少种不同的$^{\text{†}}$ 理想投票数组 $p$。

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

$^{\text{†}}$若存在某个下标 $i$，使得两个投票数组在该位置上的元素不同，则认为这两个投票数组不同。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Then $t$ test cases follow.

The first line of each test case contains two integers $n$ and $x$ ($1 \leq n \leq 10^5$, $x = 1$) — the number of voters at the polling station and Egor's favorite number.

The second line of each test case contains $n$ integers: $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 5 \cdot 10^5$) — the numbers brought by the voters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

第一行包含一个整数 $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$。

For each test case, output the number of ways modulo $10^9 + 7$ to vote so that the resulting array of votes satisfies the condition.

对于每个测试用例，输出满足条件的投票方案数对 $10^9 + 7$ 取模的结果。

null