AT_arc224_f [ARC224F] AND/OR

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots,A_N) $ と整数 $ K $ が与えられます。 はじめ、 $ x=0 $ です。 $ i=1,2,\dots,N $ の順に、以下の $ 2 $ つの操作のうち一方を選んで行います。 - 操作 $ 1 $ : $ x $ を $ x $ $ {\rm AND} $ $ A_i $ に置き換える。 - 操作 $ 2 $ : $ x $ を $ x $ $ {\rm OR} $ $ A_i $ に置き換える。 ただし、操作 $ 2 $ を選ぶ回数は全体で $ K $ 回以下でなければなりません。 ここで、 $ {\rm AND} $ はビット単位 $ {\rm AND} $ 演算を、 $ {\rm OR} $ はビット単位 $ {\rm OR} $ 演算を表します。 全ての操作が終了した時点の $ x $ として達成可能な最大値を $ M $ とします。 最終的な $ x $ が $ M $ となる操作列の個数を $ 998244353 $ で割った余りを求めてください。 ただし、 $ 2 $ つの操作列は、ある整数 $ j $ ( $ 1 \le j \le N $ ) について $ j $ 回目に選んだ操作が異なるとき、またそのときに限り区別されます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 ビット単位 $ \mathrm{AND} $ 演算とは 非負整数 $ A, B $ のビット単位 $ \mathrm{AND} $ 、 $ A\ \mathrm{AND}\ B $ は以下のように定義されます。 - $ A\ \mathrm{AND}\ B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち両方が $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3\ \mathrm{AND}\ 5 = 1 $ となります (二進表記すると: $ 011\ \mathrm{AND}\ 101 = 001 $ )。 ビット単位 $ \mathrm{OR} $ 演算とは 非負整数 $ A, B $ のビット単位 $ \mathrm{OR} $ 、 $ A\ \mathrm{OR}\ B $ は以下のように定義されます。 - $ A\ \mathrm{OR}\ B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は、 $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち少なくとも片方が $ 1 $ であれば $ 1 $ 、そうでなければ $ 0 $ である。 例えば、 $ 3\ \mathrm{OR}\ 5 = 7 $ となります (二進表記すると: $ 011\ \mathrm{OR}\ 101 = 111 $ )。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 個目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

$ T $ 行出力せよ。 $ i $ 行目には $ i $ 個目のテストケースの答えを出力せよ。

### Sample Explanation 1 この入力には $ 5 $ 個のテストケースが含まれています。 $ 1 $ 個目のテストケースについて $ M=7 $ であり、以下の $ 3 $ 通りの操作列が最終的に $ x=M $ を達成します。 - 操作を $ 1,1,2,2,2 $ の順に行う。 $ x $ は $ 0 \to 0 \to 0 \to 1 \to 3 \to 7 $ と変化する。 - 操作を $ 1,2,1,2,2 $ の順に行う。 $ x $ は $ 0 \to 0 \to 7 \to 1 \to 3 \to 7 $ と変化する。 - 操作を $ 2,1,1,2,2 $ の順に行う。 $ x $ は $ 0 \to 3 \to 3 \to 1 \to 3 \to 7 $ と変化する。 $ 5 $ 個目のテストケースについて、答えを $ 998244353 $ で割った余りを出力することに注意してください。 ### Constraints - $ 1 \le T \le 10^4 $ - $ 1 \le K \le N \le 2 \times 10^5 $ - $ 0 \le A_i < 2^{60} $ - ひとつの入力における $ N $ の総和は $ 2 \times 10^5 $ 以下 - 入力はすべて整数