Keep XOR Low

给你 $n$ 个整数 $a_1,a_2,\cdots,a_n$ 和一个整数 $x$。 你需要求出 $\{1,2,\cdots,n\}$ 的一个子集 $S$，满足 $S$ 中任意两个不同的元素 $i,j$，满足 $a_i~{\rm xor}~a_j\le x$。 求选取 $S$ 的方案数，对 $998244353$ 取模的结果。 $1\le n\le 150000,0\le a_i,x< 2^{30}$

You are given an array $ a_1, a_2, \ldots, a_n $ and an integer $ x $ . Find the number of non-empty subsets of indices of this array $ 1 \leq b_1 < b_2 < \ldots < b_k \leq n $ , such that for all pairs $ (i, j) $ where $ 1 \leq i < j \leq k $ , the inequality $ a_{b_i} \oplus a_{b_j} \leq x $ is held. Here, $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). As the answer may be very large, output it modulo $ 998\,244\,353 $ .

The first line of the input contains two integers $ n $ and $ x $ ( $ 1 \leq n \leq 150\,000 $ , $ 0 \leq x < 2^{30} $ ). Here, $ n $ is the size of the array. The next line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \leq a_i < 2^{30} $ ): the array itself.

Print one integer: the number of non-empty subsets such that the bitwise XOR of every pair of elements is at most $ x $ , modulo $ 998\,244\,353 $ .

4 2
0 1 2 3

8

3 6
4 2 2

7

4 0
1 1 2 2

6