Background

We are immature fighters, and we will never admit defeat now.

We are immature dreamers, and we will never cry now.

Problem Description

You are given an undirected complete graph $G(V,E)$ and a weight array $a$ of length $|V|$. $a_i$ represents the weight of the node with index $i$.

Define the edge value of an edge $e(u,v)$ as $val(e)$, where $val(e)=a_u\oplus a_v$, i.e., the bitwise XOR of the weights of the two endpoints. Define the weight of a spanning tree $T(V,E_t)$ of $G$ as $Val(T)$, where $Val(T)=\sum_{e\in E_t}val(e)$, i.e., the sum of edge values on the tree.

You need to compute $\sum_{T}Val(T)$, i.e., the sum of the weights of all different spanning trees in $G$.

We consider two spanning trees to be different if and only if their edge sets $E_t$ are not exactly the same, i.e., there exists at least one edge that belongs to exactly one of the two spanning trees.

Input Format

There are two lines.

The first line contains an integer $n$, denoting $|V|$, i.e., the number of nodes.

The second line contains $n$ integers, which are $a_1\sim a_n$ in order.

Output Format

Output one integer in one line, which is your answer modulo $998244353$.

3
1 2 3

12

6
1 1 4 5 1 4

19008

10
1 1 4 5 1 4 1 9 1 9

567022588

Hint

Sample #1 Explanation:

Consider that there are three spanning trees in total: $\{1-2-3\},\{1-3-2\},\{3-1-2\}$.

Their weights are $(1\oplus 2)+(2\oplus 3)=4$, $(1\oplus 3)+(3\oplus 2)=3$, and $(3\oplus 1)+(1\oplus 2)=5$.

So $4+3+5=12$.

Constraints

It is guaranteed that for all testdata, $1\le n\le 10^6$, $0\le a_i\le 10^9$. |Test Point ID|Constraints|Special Property| |:-:|:-:|:-:| |$1$||All $a_i$ are equal.| |$2\sim 5$|$n\le 4$|| |$6\sim 10$|$n\le 300$|| |$11\sim 12$|$n\le 5\times 10^4$|$a_i=[i=1]$| |$11\sim 15$|$n\le 5\times 10^4$|| |$16\sim 20$|||

Translated by ChatGPT 5