J - Wrapping
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
整数列 p に対して、以下の操作の結果できる数列 q を f(p) と定義します。
-
空の数列 q を用意する。
-
i=1,2,\ldots,|p| の順に、現在 q に p_i が存在しなければ、 q の末尾に p_i を挿入する。
正整数 N,K が与えられます。以下の条件を満たす長さ N の正整数列 a の個数を 998244353 で割った余りを求めてください。
- 1 \le a_i \le K\ (1 \le i \le N)
- f(a) = f(\mathrm{rev}(a)) が成り立つ。ただし、 \mathrm{rev}(a) = (a_N,a_{N-1},\ldots,a_1) である。
制約
- 1 \leq N,K \leq 2000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
4
条件を満たす a は (1,1,1),(1,2,1),(2,1,2),(2,2,2) の 4 通りです。
入力例 2
10 26
出力例 2
413643776