配点 : 500 点
問題文
括号顺序是
由( 和
按字典顺序比较 ) 组成的字符串。
将有效的括号序列定义为满足以下条件之一的序列:
- 空文字列
- 正确的括号顺序 A 存在并且
满足
(, A ,)的字符串 - 有效的非空括号序列 S,T 存在并且 满足S , T 的字符串
现在,N 不同的框。
你 N 框中放入正确的括号字符串。但必须满足以下两个条件。 包含在
- N 盒子中
(的总数为 它变成 M 。 - 长度是 2 \times K 不得放置在任何框中。
满足条件的进入方式总数 除以 998244353 后求余数。
但是, 运算前设定中包含的2 不同的插入方法被定义为某个框的存在以及放置在那里的不同括号。 如果正确答案是满足
制約
- 1 \leq N \leq 10^6
- 1 \leq M \leq 10^6
- 1 \leq K \leq M
部分点
- 1 \leq N,M \leq 2000 的数据集,10 点。 如果您正确回答了所有满足
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 490 点。 如果您正确回答了所有满足
入力
输入是按以下格式从标准输入给出的。
N M K
出力
将你的答案打印在一行上。
入力例 1
2 2 1
出力例 1
4
(()), 空()(), 空- 空 ,
(()) - 空 ,
()()
可以得到第 4 是的。 请注意,我们正在寻找除以
入力例 2
1 1 1
出力例 2
0
入力例 3
24 120 30
出力例 3
379268651