云浅来到了「山之心」。
这里有一个正整数 k 与 k 个正整数 N_1,N_2,⋯,N_k ,你帮她需要求出 (\sum_{x_1=0}^{N_1}\sum_{x_2=0}^{N_2}...\sum_{x_k=0}^{N_k}x_1\quad xor\quad x_2\quad xor\quad ...\quad xor\quad x_k)\quad mod\quad 998244353 的值。其中 xor 表示异或运算,即 C/C++ 中的 ^。
第一行一个正整数 k。
第二行 k 个正整数 N_1,⋯,N_k 。
输出一行一个正整数表示答案。
2 1 2
7
2 3 5
68
对于 100% 的数据, k=2,0≤N_i≤10^9 。
样例解释1
0 xor 0=0
0 xor 1=1
0 xor 2=2
1 xor 0=1
1 xor 1=0
1 xor 2=3
因此答案为 0+1+2+1+0+3=7。