Triangle
题号：NC282708
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定 n,m。

定义一个正整数序列 a 为好的，当且仅当：
  • 1\le a_i\le n。
  • a_i\le a_{i+1} 。
  • 不存在 i,j,k 满足 i<j<k 且 a_i,a_j,a_k 构成三角形。

定义 a 的权值为 \prod m^{a_i}。

求所有好的正整数序列的权值之和。答案对 998244353 取模。

1\le n\le 10^6,1\le m<998244353。

输入描述:

第一行，两个数，表示 n,m。

输出描述:

一行，一个数，表示答案。
示例1

输入

复制 
6 1

输出

复制 
66
示例2

输入

复制 
20 3

输出

复制 
128500851