P9619 Spanning Tree.

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

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.

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 one integer in one line, which is your answer modulo $998244353$.

### 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