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$ 表示按位异或运算）的最小值。

给定一个长度为 $N$ 的非负整数列 $A=(A_1, A_2, \dots, A_N)$。$A$ 的非空子序列 $B$ 一共有 $2^N-1$ 个。对于所有子序列 $B$，求 $\sum f(B)$ 并对 $998244353$ 取模后的结果。

这里按位异或运算（$\mathrm{XOR}$）是这样定义的：对于非负整数 $A, B$，$A \oplus B$ 取二进制表示时，每一位 $2^k$（$k\geq0$）的值，当且仅当 $A, B$ 在该位上有且仅有一个 $1$ 时该位为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（因为 $011 \oplus 101 = 110$）。
一般情况下，$k$ 个非负整数 $p_1, p_2, \dots, p_k$ 的按位异或为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且顺序不影响结果。

输入通过标准输入按以下格式给出：

$N \quad A_1 \quad A_2 \quad \dots \quad A_N$

请输出一行，表示答案。

样例说明 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$。

数据范围

• 输入均为整数
• $1 \leq N \leq 2000$
• $0 \leq A_i < 2^{20}$

由 ChatGPT 5 翻译