题目描述

给定 $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)：无特殊限制。