对于一个数组 $A$ 和数字 $X$，让我们定义 $f(A,X)$ 如下：
如果不能将 $A$ 拆分为几个子段使得每个子数组中所有元素的异或不等于 $X$，则 $f(A,X)=0$。
否则，$f(A,X)$ 等于这种拆分中最大可能的子段数。
给定整数 $N,K$ 和 $X$，其中 $0\leq X<2^K$。 考虑长度为 $N$ 的数组 $A$，如果每个元素都是从 $0$ 到 $2^K-1$ 均匀生成的整数。 求 $f(A,X)$ 的期望值对 $998244353$ 取模的值。
输入格式
输入的第一行包含三个整数 $N,K,X$。
输出格式
输出一行表示答案。
样例输入 1
1 3 4样例输出 1
124780545样例输入 2
2 2 1样例输出 2
561512450样例输入 3
69 42 2022样例输出 3
423858008数据范围
对于 $100\%$ 的数据，$1 \le N \le 10^6, 1 \le K \le 60, 0 \leq X < 2^K$。
各子任务的附加限制如下表所示：
| 子任务编号 | $N \leq$ | $K \leq$ | 特殊性质 | 分值 |
|---|---|---|---|---|
| 1 | $10^6$ | $60$ | $X=0$ | $10$ |
| 2 | $20$ | $4$ | - | $10$ |
| 3 | $100$ | $60$ | - | $15$ |
| 4 | $2000$ | $60$ | - | $25$ |
| 5 | $10^6$ | $60$ | - | $40$ |