题目描述

左特有 $n$ 条戒律，每条戒律可以描述为一个在 $[0,2^k-1]$ 的整数，其中第 $i$ 条戒律为 $a_i$ 。 我们称一条戒律 $x\in [0,2^k-1]$ 可以被 左特的戒律 表示当且仅当存在一个 左特的戒律 的非空子序列的异或和为 $x$ 。 作为左特的小迷妹，你忘记了 左特的戒律 ，只知道 左特的戒律 无法表示 $X$ 而且左特不说废话（ $\forall i, a_i\neq 0$ , 但可能能表示出 $0$ ）。 左特十分生气决定考考你对于每个 $t\in [0,2^k)$ 求有多少个 左特的戒律 能表示恰好 $t$ 个戒律。 左特不想为难你，决定让你输出所有答案模 $998244353$ 后的异或和即可

输入输出格式

输入一行三个整数分别表示 $n$, $k$, $X$, 意义与题面描述一致

输出格式

输出一行表示答案

样例

样例输入1：

2 3 0

样例输出1：

42

样例解释：

对于所有 $a_1\neq a_2$ 都满足条件且能表示 $3$ 种戒律 其余的不存在方案，答案即为 $42$ 异或 $0$

样例输入2：

1919 810 114514

样例输出1：

819268765

数据范围：

对于 $100\%$ 的数据满足 $1\leq n\leq 10^9,1\leq k\leq 10^6,0\leq X\leq 10^6,X < 2^k$

对于 $30\%$ 的数据满足 $n\leq 1000,k\leq 1000$

对于 $40\%$ 的数据满足 $n\leq 100000$

对于另外 $20\%$ 的数据满足 $k\leq 100000$