← 返回题目列表

AtCoder · kupc2020_m

M. 许多括号

中文机器翻译题面 查看原题

配点 : 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