你正在和朋友玩一个卡牌构建游戏。共有 $N$ 张卡牌，编号从 1 到 $N$。第 $i$ 张卡牌的数值为 $A_i$。

你需要构建两个卡组，一个给你，一个给你的朋友。每张卡牌不能同时存在于两个卡组中，且允许不使用全部 $N$ 张卡牌。卡组也可以为空，即不包含任何卡牌。

卡组的战力定义为该卡组中所有卡牌数值的按位异或和。空卡组的战力为 0。

如果两个卡组的战力相同，则称游戏是平衡的。

请计算构建两个平衡卡组的方法数。如果两个方案中至少有一个卡组包含的卡牌不同，则视为不同的方案。由于答案可能非常大，请输出答案对 998 244 353 取模的结果。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 100\,000$)。 接下来一行包含 $N$ 个整数 $A_i$ ($1 \le A_i \le 100\,000$)。

输出格式

输出一个整数，表示构建平衡卡组的方法数。请输出答案对 998 244 353 取模的结果。

样例

输入 1

4
16 12 4 8

输出 1

9

说明 1

设 $S$ 和 $T$ 分别为你和朋友的卡组集合。共有 9 种构建平衡卡组的方法： $S = \{\}$ 且 $T = \{\}$。两个卡组战力均为 0。 $S = \{2, 3, 4\}$ 且 $T = \{\}$。两个卡组战力均为 0。 $S = \{\}$ 且 $T = \{2, 3, 4\}$。两个卡组战力均为 0。 $S = \{2, 4\}$ 且 $T = \{3\}$。两个卡组战力均为 4。 $S = \{3\}$ 且 $T = \{2, 4\}$。两个卡组战力均为 4。 $S = \{2, 3\}$ 且 $T = \{4\}$。两个卡组战力均为 8。 $S = \{4\}$ 且 $T = \{2, 3\}$。两个卡组战力均为 8。 $S = \{3, 4\}$ 且 $T = \{2\}$。两个卡组战力均为 12。 * $S = \{2\}$ 且 $T = \{3, 4\}$。两个卡组战力均为 12。

输入 2

4
1 2 4 8

输出 2

1

说明 2

使游戏平衡的唯一方法是两个卡组均为空。

输入 3

2
1 1

输出 3

5

说明 3

共有 5 种构建平衡卡组的方法： $S = \{\}$ 且 $T = \{\}$。两个卡组战力均为 0。 $S = \{1, 2\}$ 且 $T = \{\}$。两个卡组战力均为 0。 $S = \{\}$ 且 $T = \{1, 2\}$。两个卡组战力均为 0。 $S = \{1\}$ 且 $T = \{2\}$。两个卡组战力均为 1。 * $S = \{2\}$ 且 $T = \{1\}$。两个卡组战力均为 1。

输入 4

6
1 1 1 2 2 2

输出 4

169