对于长度为 $n$ 的字符串 $S$，令 $S[a..b]$ 表示由位置 $a$ 到位置 $b$ 的字符组成的子串（其中 $1 \le a \le b \le n$）。此外，字符串 $S$ 的失配函数（failure function）$f : [0, n] \to [0, n-1]$ 定义如下：

$$f(i) = \max(\{0\} \cup \{j \mid S[1..j] = S[i - j + 1..i], 1 \le j < i\})$$

使用字符串 $S$ 的失配函数构建的 KMP 自动机是指以下类型的自动机。该自动机拥有 $n + 1$ 个状态 $[0..n]$，且对于每个状态 $0 \le i \le n$，存在恰好一条从 $i$ 到 $f(i)$ 的转移。

如果一个 KMP 自动机可以被嵌入到平面上，这意味着如果我们把状态 $i$ 映射到平面上的点 $(i, 0)$，并将所有转移 $i \to f(i)$ 绘制为不跨越平面上 $x$ 轴的箭头，那么可以绘制出所有 $n + 1$ 条箭头，使得除了在端点处相交外，任何两条箭头都不相交。

在使用包含 $C$ 个字母的字符集时，求长度为 $n$ 且其 KMP 自动机可以被嵌入到平面上的字符串数量，结果对 $998\,244\,353$ 取模。

字符串 $S = \text{abab}$ 的 KMP 自动机

输入格式

输入的第一行包含两个空格分隔的整数 $n$ 和 $C$，分别表示字符串的长度和字符集的大小。

输出格式

输出的第一行应包含长度为 $n$ 且其 KMP 自动机可以被嵌入到平面上的字符串数量，结果对 $998\,244\,353$ 取模。

数据范围

• $1 \le n \le 10^{18}$
• $1 \le C \le 10^9$

样例

输入样例 1

3 3

输出样例 1

27

输入样例 2

1000000000000000000 1000000000

输出样例 2

609226805