题目描述

这是简单版本。唯一区别是 $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$，则投票是理想的。请帮助他计算不同的$^{\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$ 取模。

样例

4
4 1
2 3 1 4
2 1
2 4
6 1
3 9 1 6 4 5
7 1
1 2 3 67 13 8 8

8
4
40
64