Cho số nguyên dương ~k~ và một mảng ~a~ gồm ~n~ số nguyên không âm nhỏ hơn ~2^k~. Đối với mỗi hoán vị~^*~ ~p~ gồm ~n~ phần tử từ ~1~ đến ~n~, định nghĩa:

• ~f_i(p) = a_{p_1}\ \&\ a_{p_2}\ \& \ldots \&\ a_{p_{i-1}}\ \&\ a_{p_i}~ với ~1 \le i \le n~, trong đó ~\&~ là phép toán AND bit,

• ~g(p)~ là chỉ số ~1 \le i \le n~ lớn nhất sao cho ~f_i(p) > 0~. Nếu như ~f_i(p) = 0~ với mọi ~1 \le i \le n~ thì ~g(p) = 0~.

Tính tổng của ~g(p)~ qua tất cả các hoán vị ~p~, modulo ~998\,244\,353~.

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

~^*~ Một hoán vị gồm ~n~ phầnt từ từ ~1~ đến ~n~ là dãy số chứa các số ~1, 2, \ldots, n~ theo thứ thự bất kì. Ví dụ ~[1, 3, 2, 4]~ và ~[5, 4, 1, 2, 3]~ là các hoán vị, nhưng ~[1, 4, 2]~ và ~[1, 4, 2, 2, 5]~ thì không.

Input

Mỗi test gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 10\,000~). Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~1\le n \le 2^{20}~, ~1 \le k \le 20~) – số lượng phần tử của ~a~ và giới hạn của các phần tử của ~a~ là ~2^k~.

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1,a_2,\ldots,a_n~ (~0\le a_i<2^k~).

Đảm bảo rằng:

• tổng của ~n~ qua tất cả các test case không vượt quá ~2^{20}~,

• tổng của ~2^k~ qua tất cả các test case không vượt quá ~2^{20}~.

Output

Với mỗi test case, in ra một số nguyên — tổng của ~g(p)~ qua tất cả các dãy ~p~, theo 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

Kí hiệu ~a_p = [a_{p_1}, a_{p_2}, \ldots, a_{p_n}]~.

Ở test case đầu tiên, ta có ~a = [1, 0, 1]~.

• Có 2 hoán vị ~p~ với ~g(p) = 1~ là ~p = [1, 2, 3]~ và ~p = [3, 2, 1]~. Chúng đều có ~a_p = [1, 0, 1]~.

• Có 2 hoán vị ~p~ với ~g(p) = 2~ là ~p = [1, 3, 2]~ và ~p = [3, 1, 2]~. Chúng đều có ~a_p = [1, 1, 0]~.

• Các hoán vị ~p~ còn lại có ~g(p) = 0~.

Đáp án cho test case là ~2 \cdot 1 + 2 \cdot 2 = 6~.

Ở test case thứ hai, ta có ~a~ là hoán vị của ~8~ số nguyên từ ~0~ đến ~7~. Bảng dưới đây thể hiện số lượng các hoán vị ~p~ nhóm theo giá trị ~g(p)~.

Dựa vào bảng trên, đáp án cho test case là: $$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$$