题目描述

考虑如下问题：

木棍问题

给定一个字符串 $S$。

求有多少个字符串 $T$，使得存在字符串 $A,B$ 使得：

• $A+B=T$；
• $T+T=A+S+B$。

其中 $+$ 为字符串拼接，$A,B$ 可以为空串。

给定 $n,m$。

求所有长度为 $n$，字符集为 $\{1,2,\cdots,m\}$ 中整数的字符串 $S$ 在木棍问题中答案的平方和。

答案对 $998244353$ 取模。

输入格式

一行两个整数 $n,m$。

输出格式

输出一行一个整数，为答案。

样例

4 2

202

说明/提示

对于 $100\%$ 的数据：

• $1 \le n \le 10^{11}$；
• $1 \le m \le 10^9$。

本题开启捆绑测试。

• Subtask #1（$10 \ \text{pts}$）：$n,m \le 5$。
• Subtask #2（$10 \ \text{pts}$）：$m=1$。
• Subtask #3（$20 \ \text{pts}$）：$n,m \le 10^3$。
• Subtask #4（$20 \ \text{pts}$）：$n \le 10^6$。
• Subtask #5（$40 \ \text{pts}$）：无特殊限制。