Cirno and Marisa's Game

Two players, Cirno and Marisa, play the following game on an ordered integer sequence \(V\) where each number is in the range \([1, m]\). On each turn, a player chooses an element \(x\) from \(V\) and selects an integer \(y\) satisfying \(1 \le y \le x\) and the condition \[ x \oplus y \in [0, x-1], \] where \(\oplus\) denotes the bitwise XOR operation. Then \(x\) is replaced by \(x \oplus y\) in the sequence. A move is legal only if the condition is met. The player who cannot make any move loses the game.

Assuming both players play optimally, determine the number of winning first moves for Cirno (the first player) modulo \(998244353\). A winning move is defined as a move that makes the game position losing (i.e. with a nim-sum equal to 0) for the opponent after the move.

Note: The game can be seen as a disjunctive sum of impartial games. For each element \(x\) in \(V\), let its Grundy number \(g(x)\) be defined as \[ g(x) = \text{mex}\{ g(x \oplus y) : 1 \le y \le x \text{ and } x \oplus y < x \}, \] where mex stands for the minimum excludant. The overall nim-sum is the XOR of the Grundy numbers of all elements in \(V\). A move on an element \(x\) that changes it to \(x' = x \oplus y\) is winning if \[ S \oplus g(x) \oplus g(x') = 0, \] where \(S\) is the nim-sum before the move.

inputFormat

The first line of input contains two integers \(n\) and \(m\) (the number of elements and the maximum value). The second line contains \(n\) integers \(V_1, V_2, \dots, V_n\) representing the ordered sequence \(V\). It is guaranteed that each \(V_i\) satisfies \(1 \le V_i \le m\).

outputFormat

Output a single integer, the number of winning first moves for Cirno modulo \(998244353\).

sample

1 1
1

1