问题描述

给定长为 $n$ 的序列 $m$，求序列 $a$ 的个数使得 $0 \leq a_i \leq m_i$ 且 $\bigoplus_{i = 1} ^ n a_i = 0$，对 $998244353$ 取模。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个非负整数 $m_i$。

输出格式

输出一行一个整数表示答案。

样例输入输出

样例 1 输入

3
1 2 3

样例 1 输出

6

样例 2，3

见下发文件 crystal2.in / ans 和 crystal3.in / ans。两个样例分别满足 Subtask 1 和 Subtask 3 的限制。

样例 1 说明

$(0, 0, 0)$，$(0, 1, 1)$，$(0, 2, 2)$，$(1, 1, 0)$，$(1, 0, 1)$，$(1, 2, 3)$。

数据规模与约定

• Subtask 1（10 points）：$n \leq 10$，$m_i < 4$。
• Subtask 2（15 points）：$n \leq 16$。
• Subtask 3（15 points）：保证存在位置 $i$ 使得 $m_i$ 的二进制表示位数大于其他所有 $m_j(i \neq j)$。
• Subtask 4（20 points）：$m_i < 1024$。
• Subtask 5（20 points）：$n \leq 10 ^ 3$。
• Subtask 6（20 points）：无特殊限制。

对于所有数据，$1\leq n \leq 2\times 10 ^ 5$，$0\leq m_i < 2 ^ {32}$。