Set
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Sylvy has an array a of length n. Glacy wants you to calculate \sum_{S\subseteq\left\{x|x\in Z, 1\le x\le n\right\}}\left|S\right|\left(\min_{x\in S}a_x\right)\left(\max_{x\in S}a_x\right)\left(\bigoplus_{x\in S}a_x\right) module 998244353, where \bigoplus denotes the bitwise operator xor.

输入描述:

The input is given from Standard Input in the following format:
\begin{align*}<br />&n<br />\\<br />&a_1\ a_2\ \cdots\ a_n\<br />\end{align*}

输出描述:

Print the answer as an integer.
示例1

输入

复制 
4
0 1 2 3

输出

复制 
72
示例2

输入

复制 
8
1 2 4 8 16 32 64 128

输出

复制 
46631937

说明

The answer is obvious since \bigoplus a_x=\sum a_x holds in this sample.

备注:

\begin{align*}<br />&n\le 1000000<br />\\<br />&0\le a_i\le2147483647<br />\end{align*}