配点 : 100 点
問題文
长度 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 。
一般情况 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 不依赖于顺序。
制約
- 所有输入均为整数
- 1 \leq N \leq 2000
- 0 \leq A_i < 2^{20}
入力
输入将以以下形式从标准输入给出。
N A_1 A_2 \dots A_N
出力
答案 请打印除以 1 行输出。 从
入力例 1
3 0 1 2
出力例 1
8
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 。
入力例 2
15 99412 355422 750910 993699 41414 435678 325371 637849 939332 512546 112254 175315 865362 459658 311661
出力例 2
7032514