对于一个数组 $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$。

各子任务的附加限制如下表所示：