← 返回题目列表

Codeforces · 1431/J

J. 零异或数组

中文机器翻译题面 查看原题

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。该数组是非递减的,i。 e. $$$a_1 \le a_2 \le \dots \le a_n$$$。

您必须找到大小为 $$$2n - 1$$$ 的整数数组 $$$b$$$,这样:

- $$$b_{2i-1} = a_i$$$ ($$$1 \le i \le n$$$);
- 数组 $$$b$$$ 是非递减的;
- $$$b_1 \oplus b_2 \oplus \dots \oplus b_{2n-1} = 0$$$ ($$$\oplus$$$ 表示按位异或运算:https://en.wikipedia.org/wiki/Exclusive_or。在 Kotlin 中,它是异或函数)。

计算满足上述所有条件的数组的数量,以 $$$998244353$$$ 为模。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 17$$$) — 数组 $$$a$$$ 的大小。

第二行包含 $$$n$$$ 整数 ($$$0 \le a_i \le 2^{60} - 1; a_i \le a_{i+1}$$$) — 数组 $$$a$$$ 的元素。

输出

打印一个整数 — 满足上述所有条件的数组数量,以 $$$998244353$$$ 为模。

示例

输入 #1

3
0 1 3

输出 #1

2

输入 #2

4
0 3 6 7

输出 #2

6

输入 #3

5
1 5 9 10 23

输出 #3

20

输入#4

10
39 62 64 79 81 83 96 109 120 122

输出#4

678132