思路

  此题是一个较为经典的数学问题，首先有一个前置问题，由n个相同的括号可以组成多少个不同的括号串，这个数字其实就是一个卡特兰数，并且是卡特兰数的一个经典应用之一，关于卡特兰数的计算以及证明可以自行学习，在我们知道n个相同括号能够组成不同的括号串的个数之后，再来思考如果此时有k种括号任意使用，那么不同的括号串个数将会是原来的多少，其实不难看出在一个合法的括号串当中，其中任意一个配对的括号都可以置换成k种括号中的任意一种，并且在任意置换中括号穿都不会相同，所以显然括号串的数量将会扩充为原来的k^n^倍，所以n个k种类的括号任意组合最终不同的合法括号串数量即为n的卡特兰数*k^n^

代码

python

mod = 998244353
N = 10010
d = [0] * N
n, k = map(int, input().split())

题目内容

程序语言中有各种各样的括号，比如圆括号$()$,方括号$[]$,花括号$<>$,等等。

如果一个括号串$s$满足下列三个条件中的至少一个，则我们认为该括号串是合法的。

$1$.该括号串是空串。

$2$.该括号串行如$atb$,其中$a$和$b$是一对可以匹配的括号（即$a$和$b$是同一种括号，且$a$为左括号$b$为右括号），而$t$是一个合法的括号。

$3$.该括号串形如$t1t2$，其中$t$和$t2$都是合法括号串。

例$1$：由条件$2$，$()$是合法的括号串。其中a=(,b=),t为空串。

例$2$：由条件$2$，$<0>$是合法的括号串，其中$a=<,b=>,t=0$。

例$3$：由条件$3$，$[]<0>$是合法的括号串，其中$t1=[],t2=<0>$。

例$4$：}{，()和))(不是合法的括号串。 现在给出可以使用的括号种类$k$，请你求出使用$k$括号可以组成几个长度为$n$的不同的合法括号串。

输入描述

第一行有两个正整数，$n$($1<=n<=10000$)和$k$($1<=k<=10$)。其中$n$为括号串的长度，$k$为允许使用的括号种类。输入保证$n$为偶数

输出描述

输出仅使用$k$括号可以组成几种长度为$n$的不同的合法括号串。因为答案很大，你只需要输出答案除以$998244353$所得的余数

样例1

输入

6 2

输出

40