AT_utpc2022_m Minimize XOR by Redistribution

長さ $ n $ の非負整数列 $ X=(X_1,X_2,\dots,X_n) $ に対し $ f(X) $ を、 $ Y_1+Y_2+\dots+Y_n=X_1+X_2+\dots+X_n $ を満たす長さ $ n $ の非負整数列 $ Y=(Y_1,Y_2,\dots,Y_n) $ 全てにおける $ Y_1 \oplus Y_2 \oplus \dots \oplus Y_n $ の最小値とします。ただしここで、 $ \oplus $ はビット単位 $ \mathrm{XOR} $ 演算を表します。 長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 $ A $ の空でない部分列 $ B $ は $ 2^N-1 $ 個考えられますが、それらすべてに対する $ f(B) $ の総和を $ 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 $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 $ A $ の空でない 部分列 $ B $ は $ B=(0),(1),(2),(0,1),(0,2),(1,2),(0,1,2) $ の $ 7 $ 個存在します。 例えば $ B=(0,2) $ のとき、 $ 1+1=0+2,\ 1 \oplus 1 = 0 $ であるため $ f(B)=0 $ です。 上記の $ 7 $ 個の $ A $ の部分列に対する $ f(B) $ は順に $ 0,1,2,1,0,3,1 $ となるため、答えは $ 0+1+2+1+0+3+1=8 $ となります。 ### Constraints - 入力は全て整数 - $ 1 \leq N \leq 2000 $ - $ 0 \leq A_i < 2^{20} $