给定一个数组 $$$a_1, a_2, \ldots, a_n$$$ 和一个整数 $$$x$$$。
求此数组 $$$1 \leq b_1 < b_2 < \ldots < b_k \leq n$$$ 索引的非空子集的数量,这样对于所有对 $$$(i, j)$$$ 其中 $$$1 \leq i < j \leq k$$$,不等式 $$$a_{b_i} \oplus a_{b_j} \leq x$$$ 被持有。这里,$$$\oplus$$$表示按位异或运算。由于答案可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \leq n \leq 150\,000$$$, $$$0 \leq x < 2^{30}$$$)。这里,$$$n$$$ 是数组的大小。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{30}$$$):数组本身。
输出
打印一个整数:非空子集的数量,使得每对元素的按位异或最多为 $$$x$$$,模 $$$998\,244\,353$$$。
示例
输入 #1
4 2 0 1 2 3
输出 #1
8
输入 #2
3 6 4 2 2
输出 #2
7
输入 #3
4 0 1 1 2 2
输出 #3
6