题目描述

给定一个长度为 $n$ 的序列 $a[1...n]$，定义函数 $f(b[1...m])$ 的值为在 $[0,m-1]$ 内满足如下条件的 i 的数目：$b$ 中前 i 个数异或起来的值小于 $b$ 中前 $i+1$ 个数异或起来的值。

对于 $a[1...n]$ 的每个子序列 $b[1...m]$，求 $f(b[1...m])$ 之和，答案对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

接下来一行，共 $n$ 个整数 $a_1, a_2, ..., a_n$。

输出格式

一个整数表示答案。

输入输出样例 #1

输入 #1

5
1 2 3 4 5

输出 #1

64

说明/提示

共 $10$ 个测试点。

测试点 $1,2$ 满足 $n \leq 20$。

测试点 $3,4$ 满足 $n \leq 1000$。

测试点 $5,6$ 满足 $a_i \leq 2^8 - 1$。

对于所有数据，满足 $1 \leq n \leq 10^5, 0 \leq a_i \leq 2^{30} - 1$。