#P1336E1. Chiori and Doll Picking (easy version)
Chiori and Doll Picking (easy version)
Description
This is the easy version of the problem. The only difference between easy and hard versions is the constraint of $m$. You can make hacks only if both versions are solved.
Chiori loves dolls and now she is going to decorate her bedroom!
As a doll collector, Chiori has got $n$ dolls. The $i$-th doll has a non-negative integer value $a_i$ ($a_i < 2^m$, $m$ is given). Chiori wants to pick some (maybe zero) dolls for the decoration, so there are $2^n$ different picking ways.
Let $x$ be the bitwise-xor-sum of values of dolls Chiori picks (in case Chiori picks no dolls $x = 0$). The value of this picking way is equal to the number of $1$-bits in the binary representation of $x$. More formally, it is also equal to the number of indices $0 \leq i < m$, such that $\left\lfloor \frac{x}{2^i} \right\rfloor$ is odd.
Tell her the number of picking ways with value $i$ for each integer $i$ from $0$ to $m$. Due to the answers can be very huge, print them by modulo $998\,244\,353$.
The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 35$) — the number of dolls and the maximum value of the picking way.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^m$) — the values of dolls.
Print $m+1$ integers $p_0, p_1, \ldots, p_m$ — $p_i$ is equal to the number of picking ways with value $i$ by modulo $998\,244\,353$.
Input
The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m \le 35$) — the number of dolls and the maximum value of the picking way.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^m$) — the values of dolls.
Output
Print $m+1$ integers $p_0, p_1, \ldots, p_m$ — $p_i$ is equal to the number of picking ways with value $i$ by modulo $998\,244\,353$.
Samples
4 4
3 5 8 14
2 2 6 6 0
6 7
11 45 14 9 19 81
1 2 11 20 15 10 5 0