Migrated from Lutece 1171 两句话题意

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

记一个集合的最大公约数为该集合内所有数的最大公约数，求一个给定集合的非空子集的最大公约数的 $k$ 次方的期望。

Input

第一行有一个数 $t$，表示数据组数。

接下来每组数据两行，第一行两个整数 $n,k$ ($1\le n,k\le 10^6$)，表示该集合有 $n$ 个整数。

第二行有 $n$ 个整数 $a_i$ ($0\le a_i\le 2\times 10^6$)，代表该集合内的所有元素。

Output

每组数据输出一行，为期望乘上 $2^n-1$，之后取模 $10^7+7$ 的结果。

Samples

2
5 1
1 2 3 4 5
3 2
2 3 6

42
64

Note

样例 2 中最大公约数为 $1$ 的非空子集集有 $\{2,3\},\{2,3,6\}$ 两个，$2$ 的有 $\{2\},\{2,6\}$ 两个，$3$ 的有 $\{3\},\{3,6\}$ 两个，$6$ 的有 $\{6\}$ 一个。

所以期望是 $(2\times 1^2+2\times 2^2+2\times 3^2+1\times 4^2)/7=64/7$。

Resources

2015 UESTC ACM Training for Math