T1
题目描述
小 Z 有一个长度为 $n$ 的非负整数序列 $a$ ，定义一个合法的长度为 $n$ 的非负整数序列 $b$ 为满足对于任意的 $1 \leq i \leq n$ ，均满足 $0 \leq b_i \leq a_i$ 。
小 Z 想知道所有长度为 $n$ 的满足序列异或和为 $0$ 的合法序列 $b$ 的数量，对 $998244353$ 取模。
时间限制 2 s ，空间限制 512 MB 。
输入格式
输入的第一行包含一个整数 $n$ ，表示序列 $a$ 的长度。
输入的第二行包含 $n$ 个整数，其中第 $i$ 个数输入的数表示 $a_i$ 的值。
输出格式
输出一行包含一个整数，表示答案对 $998244353$ 取模后的结果。
样例 1 输入
5
2 2 3 2 3样例 1 输出
108样例 2 输入
8
6 5 4 9 6 10 2 2样例 2 输出
115804数据范围
对于所有数据，保证 $1 \leq n \leq 10^5 , 0 \leq a_i \leq 10^9$ 。
| 测试点编号 | $n \leq$ | $a_i \leq$ | 特殊性质 |
|---|---|---|---|
| $1$ | $10$ | $5$ | 无 |
| $2 \sim 3$ | $10^5$ | $50$ | 无 |
| $4 \sim 6$ | $10^5$ | $10^9$ | A |
| $7 \sim 8$ |
$2000$ | $10^9$ | 无 |
| $9 \sim 10$ | $10^5$ | $10^9$ | 无 |
特殊性质 A ：保证 $a_1 > 2 \max_{i=2}^n \{ a_i \}$ 。
