B. Beautiful XOR Problem
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a sequence of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ and a positive integer $$$k$$$.

Count the number of subsequences $$$b_1, b_2, \dots, b_l$$$ of $$$a$$$ with length $$$l$$$ such that $$$b_1 \oplus b_2 \oplus \dots \oplus b_l = 0$$$ (where $$$\oplus$$$ denotes bitwise XOR) and $$$l$$$ is divisible by $$$k$$$.

Here, $$$b$$$ is a subsequence of $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements.

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^6$$$, $$$1 \leq k \leq 20$$$).

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^6$$$).

Output

Print an integer — the number of subsequences satisfying the constraints. Since the answer can be very large, print it modulo $$$998244353$$$.

Example
Input
5 3
1 1 3 4 5
Output
3