AT_arc222_e [ARC222E] XOR Matching

$ N $ 枚のカードがあります． $ i $ 番目のカード（ $ 1\leq i\leq N $ ）には整数 $ A_i $ が書かれています．ここで， $ 0\leq A_i \leq 2^M-1 $ が成り立ちます． 各整数 $ X=0,1,\ldots,2^M-1 $ に対して，次の問題の答えを $ f(X) $ と書くことにします． > カードのペアをいくつか作ることを考えます． > > ただし，ペアは相異なる $ 2 $ 枚のカードからなり，それら $ 2 $ 枚のカードに書かれた整数のビット単位 XOR が $ X $ となる必要があります． 同じカードを複数のペアに含めることはできません． > > この条件のもとで作れるペアの個数の最大値を求めてください． 次の値を出力してください． \\\[ \\left(\\sum\_{X=0}^{2^M-1} f(X) \\times 10 ^ X\\right) \\bmod 998244353 \\\] ビット単位 $ \mathrm{XOR} $ 演算とは 非負整数 $ A, B $ のビット単位 $ \mathrm{XOR} $ ， $ A \oplus B $ は，以下のように定義されます． - $ A \oplus B $ を二進表記した際の $ 2^k $ ( $ k \geq 0 $ ) の位の数は， $ A, B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $ ，そうでなければ $ 0 $ である． 例えば， $ 3 \oplus 5 = 6 $ となります (二進表記すると: $ 011 \oplus 101 = 110 $ )． 一般に $ k $ 個の非負整数 $ p_1, p_2, p_3, \dots, p_k $ のビット単位 $ \mathrm{XOR} $ は $ (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) $ と定義され，これは $ p_1, p_2, p_3, \dots, p_k $ の順番によらないことが証明できます．

入力は以下の形式で標準入力から与えられます． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

次の値を出力してください． \\\[ \\left(\\sum\_{X=0}^{2^M-1} f(X) \\times 10 ^ X\\right) \\bmod 998244353 \\\]

### Sample Explanation 1 - $ X=0 $ の場合： $ (A_1,A_2) $ ， $ (A_3,A_4) $ という $ 2 $ 個のペアを作ることができます． - $ X=1 $ の場合： $ 0 $ 個のペアを作ることができます． - $ X=2 $ の場合： $ (A_1,A_4) $ ， $ (A_2,A_3) $ という $ 2 $ 個のペアを作ることができます． - $ X=3 $ の場合： $ 0 $ 個のペアを作ることができます． したがって， $ f(0)=2 $ ， $ f(1)=0 $ ， $ f(2)=2 $ ， $ f(3)=0 $ です．出力すべき値は $ 2\times 1 + 0\times 10 + 2\times 100 + 0\times 1000 = 202 $ です． ### Constraints - $ 2\leq N\leq 2\times 10^5 $ - $ 1\leq M\leq 20 $ - $ 0\leq A_i \leq 2^M-1 $ ( $ 1\leq i\leq N $ ) - 入力される値はすべて整数．