您正在与朋友玩牌组构建游戏。有 $$$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
输入 #2
4 1 2 4 8
输出 #2
1
输入 #3
2 1 1
输出 #3
5
输入#4
6 1 1 1 2 2 2
输出#4
169
注意
示例输入/输出 #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 的说明
使游戏平衡的唯一方法是将两副牌都清空。
示例输入/输出 #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$$$。