题目描述

作曲系统使用正整数序列 $a_1,a_2,\ldots,a_k$ 表示一段旋律，其中序列长度 $k$ 可以是任意正整数。

一段旋律被称为阶梯乐章，当且仅当满足：

• 所有音符均为正整数；

• 所有音符之和为 $n$，即

  $$\sum_{i=1}^{k}a_i=n;$$

• 任意相邻两个音符的数值恰好相差 $1$。

对于一个阶梯乐章 $p_1,p_2,\ldots,p_k$，定义它的下降次数为

该乐章的权值为 $w^{f(p)}$，其中 $w$ 是给定常数。特别地，本题规定 $0^0=1$。

请计算所有阶梯乐章的权值之和，并输出其对 $998244353$ 取模后的结果。

输入格式

一行包含两个整数 $n,w$，分别表示所有音符之和以及权值参数。

输出格式

输出一行一个整数，表示所有阶梯乐章的权值之和对 $998244353$ 取模后的结果。

样例

样例输入 1

5 2

样例输出 1

6

样例解释 1

阶梯乐章共有 $[2,1,2],[2,3],[3,2],[5]$。它们的下降次数依次为 $1,0,1,0$，权值依次为 $2,1,2,1$，因此答案为 $6$。

数据范围与提示

对于所有测试点，$1\leq n\leq 2\times 10^5$，$0\leq w<998244353$。