For an array $A$ and a number $X$, let us define $f(A,X)$ as follows:
If it is impossible to partition $A$ into several subsegments such that the XOR sum of all elements in each subsegment is not equal to $X$, then $f(A,X)=0$.
Otherwise, $f(A,X)$ is equal to the maximum possible number of subsegments in such a partition.
Given integers $N, K$, and $X$, where $0\leq X<2^K$. Consider an array $A$ of length $N$, where each element is an integer uniformly generated from $0$ to $2^K-1$. Find the expected value of $f(A,X)$ modulo $998244353$.
Input
The first line of input contains three integers $N, K, X$.
Output
Output one line representing the answer.
Examples
Input 1
1 3 4
Output 1
124780545
Input 2
2 2 1
Output 2
561512450
Input 3
69 42 2022
Output 3
423858008
Constraints
For $100\%$ of the data, $1 \le N \le 10^6, 1 \le K \le 60, 0 \leq X < 2^K$.
The additional constraints for each subtask are as follows:
| Subtask ID | $N \leq$ | $K \leq$ | Special Property | Score |
|---|---|---|---|---|
| 1 | $10^6$ | $60$ | $X=0$ | $10$ |
| 2 | $20$ | $4$ | - | $10$ |
| 3 | $100$ | $60$ | - | $15$ |
| 4 | $2000$ | $60$ | - | $25$ |
| 5 | $10^6$ | $60$ | - | $40$ |