GCD Expectation

Time Limit: 4 Seconds
Memory Limit: 262144 KB

Edward has a set of `n` integers {`a`_{1}, `a`_{2},...,`a`_{n}}. He randomly picks a nonempty subset {`x`_{1}, `x`_{2},…,`x`_{m}} (each nonempty subset has equal probability to be picked), and would like to know the expectation of [**gcd**(`x`_{1}, `x`_{2},…,`x`_{m})]^{k}.

Note that **gcd**(`x`_{1}, `x`_{2},…,`x`_{m}) is the greatest common divisor of {`x`_{1}, `x`_{2},…,`x`_{m}}.

#### Input

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains two integers `n`, `k` (1 ≤ `n`, `k` ≤ 10^{6}). The second line contains `n` integers `a`_{1}, `a`_{2},…,`a`_{n} (1 ≤ `a`_{i} ≤ 10^{6}).

The sum of values max{`a`_{i}} for all the test cases does not exceed 2000000.

#### Output

For each case, if the expectation is `E`, output a single integer denotes `E` · (2^{n} - 1) modulo 998244353.

#### Sample Input

1
5 1
1 2 3 4 5

#### Sample Output

42

Author:

**LIN, Xi**
Source:

**The 15th Zhejiang University Programming Contest**
Submit
Status