UOJ Logo

NOI.AC

2S 512MB

#3566. T1

Statistics

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 \}$ 。