UOJ Logo

NOI.AC

2S 512MB

#3566. T1

统计

T1

题目描述

小 Z 有一个长度为 n 的非负整数序列 a ,定义一个合法的长度为 n 的非负整数序列 b 为满足对于任意的 1in ,均满足 0biai

小 Z 想知道所有长度为 n 的满足序列异或和为 0 的合法序列 b 的数量,对 998244353 取模。

时间限制 2 s ,空间限制 512 MB 。

输入格式

输入的第一行包含一个整数 n ,表示序列 a 的长度。

输入的第二行包含 n 个整数,其中第 i 个数输入的数表示 ai 的值。

输出格式

输出一行包含一个整数,表示答案对 998244353 取模后的结果。

样例 1 输入

5
2 2 3 2 3

样例 1 输出

108

样例 2 输入

8
6 5 4 9 6 10 2 2

样例 2 输出

115804

数据范围

对于所有数据,保证 1n105,0ai109

测试点编号 n ai 特殊性质
1 10 5
23 105 50
46 105 109 A
78
2000 109
910 105 109

特殊性质 A :保证 a1>2max