该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：fusion.in

输出：fusion.out

题目描述

有 $n$ 个球排成一行，每个球的颜色属于 $1\sim k$。

你要进行 $n-1$ 轮合成操作。每一轮选择两个相邻的球合成为一个新球，新球颜色必须从这两个球原本颜色中二选一。

经过 $n-1$ 轮后会只剩下一个球。请你统计：有多少种初始颜色序列，能够通过某种合成过程，最终得到颜色为 $1$ 的球。

若两个初始序列在某个位置颜色不同，则视为不同方案。答案对 $998244353$ 取模。

输入格式

输入一行两个整数 $n,k$。

其中 $n$ 可能非常大，以十进制整数形式给出。

输出格式

输出一个整数，表示满足条件的初始序列数量对 $998244353$ 取模后的结果。

输入输出样例

10 3

58025

说明/提示

数据范围：$1 \le n \le 10^{1000000}$，$2 \le k \le 10^6$。