Description

总所周知，jbgg 不会数学，一天 jbgg 求着磊神教他位运算，磊神就给了一个长度为 $n$ 的非负整数序列 $\{a_i\}$。磊神会随便挑几个下标，jbgg 需要说出对应下标的数字异或后的数。只选择一个下标时，异或结果为它本身。

假设磊神给出的序列 $\{a_i\}$ 为 $\{2,4,2,5,3,5\}$，磊神选择下标 $1,2,5$，那么 jbgg 需要给出对应的结果 $a_1 \oplus a_2 \oplus a_5 = 2 \oplus 4 \oplus 3 = 5$。

由于 jbgg 太笨了，每次都答错，于是愤怒的磊神要求 jbgg 算出所有不同下标选法的结果把它们加起来，但 jbgg 想快点回去打音游，你能帮帮 jbgg 吗？

两种下标的选法不同，当且仅当两个选法中至少有一个下标不同。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模的结果。

Format

Input

第一行包含一个正整数 $n$ $(1 \leqslant n \leqslant 10^5)$，表示序列 $\{a_i\}$ 的长度。

第二行包含 $n$ 个整数 $a_1,a_2, \cdots, a_n$ $(0 \leqslant a_i < 2^{21})$。

Output

输出包含一个正整数, 为你的答案对 $998244353$ 取模的结果。

Samples

3
3 5 2

28

2
114514 1919810

3931812

5
1 2 3 4 5

112

Notes

异或：对于 $c = a \oplus b$，若 $a$ 和 $b$ 二进制下对应 bit 位不同，则为 $1$，否则为 $0$。在 C 语言中，用 a ^ b 来表示。

比如 $5 \oplus 6 = 101_2 \oplus 110_2 = 011_2 = 3$。

第一个样例，所有的选法如下：

$$a_1 = 3\\ a_2 = 5\\ a_3 = 2\\ a_1 \oplus a_2 = 3 \oplus 5 = 6\\ a_1 \oplus a_3 = 3 \oplus 2 = 1\\ a_2 \oplus a_3 = 5 \oplus 2 = 7\\ a_1 \oplus a_2 \oplus a_3 = 3 \oplus 5 \oplus 2 = 4\\ $$

所以答案为 $3 + 5 + 2 + 6 + 1 + 7 + 4 = 28$。

Limitation

1s, 1024KiB for each test case.