题目描述
给定 $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):无特殊限制。