给定 $n, d$，计算

$$\mathrm{ans} = \sum_{0 \leq x,y,z < n} (x \oplus y \oplus z)^d \bmod{998\,244\,353}$$

输入格式

两个整数 $n, d$。

输出格式

输出整数 $\mathrm{ans}$。

样例数据

样例输入

10 3

样例输出

718116

子任务

对于子任务 1（$10\%$）：$0 < n \leq 300$，$d \leq 3$。

对于子任务 2（$10\%$）：$0 < n \leq 5\,000$，$d \leq 3$。

对于子任务 3（$20\%$）：$0 < n \leq 10^5$，$d \leq 3$。

对于子任务 4（$20\%$）：$0 < n \leq 2^{30}$，$d \leq 3$。

对于子任务 5（$20\%$）：$0 < n \leq 2^{30}$，$d \leq 10$。

对于子任务 6（$20\%$）：$0 < n \leq 2^{30}$，$d \leq 10^5$。