题目描述

给定整数 $n,k$，求有多少个长度大于 $1$ 的自然数序列 $a$ 满足：

1. 设序列长度为 $m$（下标从 $1$ 开始），则

   $$\sum_{i=1}^{m} k^{a_i} \le k^n.$$

2. 对任意 $1\le i<m$，均满足

   $$a_i\le a_{i+1}\le a_i+1.$$

3. $a_1=0$，$a_m=n-1$。

由于答案可能很大，请对 $998244353$ 取模后输出。

输入格式

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

输出格式

输出一行一个整数，表示答案对 $998244353$ 取模后的结果。

样例 1

样例输入 1

2 3

样例输出 1

9

样例解释 1

一共有 $9$ 种合法序列：

[0, 1]
[0, 0, 1]
[0, 0, 0, 1]
[0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 1]
[0, 1, 1]
[0, 0, 1, 1]
[0, 0, 0, 1, 1]

样例 2

样例输入 2

4 4

样例输出 2

20320

样例 3

样例输入 3

80 3

样例输出 3

726272043

样例 4

样例输入 4

114 514

样例输出 4

655512077

数据范围

对于所有数据，保证：