Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
Statistics

题目描述

给定 $n$ 个数 $a_i$,要求将每个数分到第一组或第二组,使得:
- 没有组为空;
- 两个组内所有数的按位或相等。
求方案数,对 $998244353$ 取模。

输入格式

第一行:一个整数 $n$。 第二行:$n$ 个整数 $a_i$。

输出格式

第一行:一个整数表示答案。

样例输入 1

4
3 5 6 7

样例输出 1

8

样例解释 1

$[{3,5},{6,7}],[{3,5,6},{7}],[{3,6},{5,7}],[{3,7},{5,6}],[{5,6},{3,7}],[{5,7},{3,6}],[{6,7},{3,5}],[{7},{3,5,6}]$

数据范围

对于全部数据, $1\leq n \leq 2\times10^5,0\leq a_i < 2^{21}$。
Subtask 1 (20 pts): $n\leq20$;
Subtask 2 (20 pts): $0\leq a_i<2^4$;
Subtask 3 (20 pts): $n\leq1000,0\leq a_i 2^{10}$;
Subtask 4 (20 pts): $0\leq a_i < 2^{12}$;
Subtask 5 (20 pts):无特殊限制。