Problem Description

Given an undirected complete graph \( G(V,E) \) and an array of weights \( a \) of length \( |V| \). \( a_i \) represents the weight of the node numbered \( i \).

Define the edge value \( val(e) \) of an edge \( e(u,v) \) as \( val(e) = a_u \oplus a_v \), which is the XOR sum of the weights of the two nodes connected by the edge. Define the value \( Val(T) \) of a spanning tree \( T(V,E_t) \) of \( G \) as \( Val(T) = \sum_{e \in E_t} val(e) \), which is the sum of the edge weights in the tree.

You need to find \( \sum_{T} Val(T) \), which is the sum of the values of all distinct spanning trees in \( G \).

Two spanning trees are considered different if and only if their edge sets \( E_t \) are not identical, meaning there exists at least one edge that is present in only one of the two trees.

Input Format

The input consists of two lines.

The first line contains an integer \( n \), representing the number of nodes \( |V| \).

The second line contains \( n \) integers, representing \( a_1 \) to \( a_n \).

Output Format

Output a single integer, which is your answer modulo \( 998244353 \).

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

12

Sample Input #2

6
1 1 4 5 1 4

Sample Output #2

19008

Sample Input #3

10
1 1 4 5 1 4 1 9 1 9

Sample Output #3

567022588

Notes

Sample #1 Explanation:

Consider there are three spanning trees: \( \{1-2-3\}, \{1-3-2\}, \{3-1-2\} \).

Their values are \( (1 \oplus 2) + (2 \oplus 3) = 4 \), \( (1 \oplus 3) + (3 \oplus 2) = 3 \), \( (3 \oplus 1) + (1 \oplus 2) = 5 \).

Thus, \( 4 + 3 + 5 = 12 \).

Data Constraints

For all data, \( 1 \le n \le 10^6 \), \( 0 \le a_i \le 10^9 \).

见题面 Input 部分

见题面 Output 部分