시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 4 4 50.000%

## 문제

Zhong Ziqian got an integer array a1, a2, . . . , an and an integer x as birthday presents.

Every day after that, he tried to find a non-empty subsequence of this array 1 ≤ b1 < b2 < . . . < bk ≤ n, such that for all pairs (i, j) where 1 ≤ i < j ≤ k, the inequality abi ⊕ abj ≥ x held. Here, ⊕ is the bitwise exclusive-or operation.

Of course, every day he must find a different subsequence.

How many days can he do this without repeating himself? As this number may be very large, output it modulo 998 244 353.

## 입력

The first line of the input contains two integers n and x (1 ≤ n ≤ 300 000, 0 ≤ x ≤ 260 − 1). Here, n is the size of the array.

The next line contains n integers a1, a2, . . . , an: the array itself (0 ≤ ai ≤ 260 − 1).

## 출력

Output one integer: the number of subsequences of Ziqian’s array such that bitwise xor of every pair of elements is at least x, modulo 998 244 353.

## 예제 입력 1

3 0
0 1 2


## 예제 출력 1

7


## 예제 입력 2

3 2
0 1 2


## 예제 출력 2

5


## 예제 입력 3

3 3
0 1 2


## 예제 출력 3

4


## 예제 입력 4

7 4
11 5 5 8 3 1 3


## 예제 출력 4

35


## 힌트

In the first example, all 23 − 1 non-empty subsequences are suitable.

in the second example, two non-empty subsequences are not suitable, it is b = [1, 2] and b = [1, 2, 3], that is because a1 ⊕ a2 = 0 ⊕ 1 = 1 which is smaller than 2.

In the third example, b = , b = , b = , b = [2, 3] are suitable.

## 출처

• 문제를 만든 사람: 300iq