You have been given an array $A$ of size $N$. Now, let's call the weight of a subsequence the xor of all elements it contains.The weight of a subsequence containing $0$ elements is $0$. Now, you need to find the summation of xor of each subsequence $\times$ the length of the subsequence over all $2^N$ subsequences of the given array $A$.

As the answer can be rather large, print it Modulo $998244353$

Can you do it ?

Input Format :

The first line contains a single integer $N$ denoting the size of the given array $A$. The next line contains $N$ integers, where the $i^{th}$ integer denotes $A[i]$.

Output Format:

Print a single integer denoting the answer. As the answer can be rather large, print it Modulo $998244353$

Input Constraints :

$1 \le N \le 5 \cdot 10^5$

$0 \le A[i] \le 10^{18}$

Note that the Expected Output Feature for Custom Invocation is not supported for this contest.