给定一个整数数组 $$$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