Description

有三个人组队进行一个 project，project 包含了 $n$ 个环节，依次进行。每个环节结束时，该队都会立刻得知并获得这个环节的分数。

每个环节的分数只能属于一个人，但是三个人可以自行谎报分工决定这个环节的分数属于哪一个人。每个人当前的分数为属于这个人的环节的分数的异或和（若这个人没有认领任何环节的分数，则为 $0$）。

为了保证三人《关 系 良 好》以及最终的分数《公 平》，在 project 进行的任意时刻（包含完全结束），三个人的分数至少要有两个是相同的。

你需要求出有多少种认领分数的方案，使得上述条件成立。答案对 $998244353$ 取模。

Format

Input

第一行输入一个正整数 $n\,(1\leq n\leq 2\times 10^5)$ 表示 project 的环节数。

第二行输入 $n$ 个正整数表示每个环节的分数 $a_i\,(1\leq a_i < 2^{30})$。

Output

仅一个非负整数，表示方案数，对 $998244353$ 取模。

Samples

4
1 2 2 1

9

前三个环节由同一人认领，第四个环节由一人认领，共 $3\times3=9$ 种方案。可以证明不存在其他合法方案。

5
1 2 3 3 2

39

Limitation

1s, 256MiB.