Problem Statement

There are $N$ cards. The $i$-th card ($1\leq i\leq N$) has the integer $A_i$ written on it. Here, $0\leq A_i \leq 2^M-1$ holds.

For each integer $X=0,1,\ldots,2^M-1$, let $f(X)$ denote the answer to the following problem:

Consider forming some pairs of cards.

Each pair consists of two distinct cards, and the bitwise XOR of the integers written on those two cards must equal $X$. The same card cannot be included in multiple pairs.

Find the maximum number of pairs that can be formed under these conditions.

Output the following value:

[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 ]

What is the bitwise $\mathrm{XOR}$ operation The bitwise $\mathrm{XOR}$ of non-negative integers $A, B$, $A \oplus B$, is defined as follows. The digit at the $2^k$ ($k \geq 0$) place of $A \oplus B$ in binary representation is $1$ if exactly one of the digits at the $2^k$ place of $A$ and $B$ in binary representation is $1$, and $0$ otherwise. For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$). In general, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

Constraints

• $2\leq N\leq 2\times 10^5$
• $1\leq M\leq 20$
• $0\leq A_i \leq 2^M-1$ ($1\leq i\leq N$)
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N

Output

Output the following value:

[ \left(\sum_{X=0}^{2^M-1} f(X) \times 10 ^ X\right) \bmod 998244353 ]