Given a positive integer ~k~ and an array ~a~ consisting of ~n~ non-negative integers less than ~2^k~. For each permutation~^*~ ~p~ consisting of ~n~ elements from ~1~ to ~n~, define:

• ~f_i(p) = a_{p_1}\ \&\ a_{p_2}\ \& \ldots \&\ a_{p_{i-1}}\ \&\ a_{p_i}~ for ~1 \le i \le n~, where ~\&~ is the bitwise AND operation,

• ~g(p)~ is the index ~1 \le i \le n~ largest such that ~f_i(p) > 0~. If ~f_i(p) = 0~ for all ~1 \le i \le n~, then ~g(p) = 0~.

Calculate the sum of ~g(p)~ over all permutations ~p~, modulo ~998\,244\,353~.

———————————————————————–

~^*~ A permutation of ~n~ elements from ~1~ to ~n~ is a sequence containing the numbers ~1, 2, \ldots, n~ in any order. For example, ~[1, 3, 2, 4]~ and ~[5, 4, 1, 2, 3]~ are permutations, but ~[1, 4, 2]~ and ~[1, 4, 2, 2, 5]~ are not.

Input

Each test consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 10\,000~). The description of each test case is as follows.

The first line contains two integers ~n~ and ~k~ (~1\le n \le 2^{20}~, ~1 \le k \le 20~) – the number of elements in ~a~ and the limit of the elements in ~a~ is ~2^k~.

The second line contains ~n~ non-negative integers ~a_1,a_2,\ldots,a_n~ (~0\le a_i<2^k~).

It is guaranteed that:

• the sum of ~n~ across all test cases does not exceed ~2^{20}~,

• the sum of ~2^k~ across all test cases does not exceed ~2^{20}~.

Output

For each test case, print an integer — the sum of ~g(p)~ over all permutations ~p~, modulo ~998\,244\,353~.

Scoring

Sample Input 1

2
3 1
1 0 1
8 3
0 1 2 3 4 5 6 7

Sample Output 1

6
67248

Notes

Let ~a_p = [a_{p_1}, a_{p_2}, \ldots, a_{p_n}]~.

In the first test case, we have ~a = [1, 0, 1]~.

• There are 2 permutations ~p~ with ~g(p) = 1~, which are ~p = [1, 2, 3]~ and ~p = [3, 2, 1]~. Both have ~a_p = [1, 0, 1]~.

• There are 2 permutations ~p~ with ~g(p) = 2~, which are ~p = [1, 3, 2]~ and ~p = [3, 1, 2]~. Both have ~a_p = [1, 1, 0]~.

• The remaining permutations ~p~ have ~g(p) = 0~.

The answer for the test case is ~2 \cdot 1 + 2 \cdot 2 = 6~.

In the second test case, we have ~a~ as a permutation of ~8~ integers from ~0~ to ~7~. The table below shows the number of permutations ~p~ grouped by the value of ~g(p)~.

Based on the table above, the answer for the test case is: $$5040 \cdot 0 + 13680 \cdot 1 + 12960 \cdot 2 + 6912 \cdot 3 + 1728 \cdot 4 + 0 \cdot 5 + 0 \cdot 6 + 0 \cdot 7 + 0 \cdot 8 = 67248$$