AT_kupc2020_m.Many Parentheses

括号序列是由 ( 和 ) 组成的字符串。我们将满足以下任一条件的序列称为正确的括号序列：

• 空字符串
• 存在一个正确的括号序列 $A$，使得 (, $A$, ) 按序连接构成新的序列
• 存在非空的正确括号序列 $S$ 和 $T$，使得 $S$, $T$ 连接形成新的序列

现在有 $N$ 个不同的盒子，你希望向每个盒子中放入一个正确的括号序列，但必须满足这两个条件：

1. 所有盒子中 ( 的总个数为 $M$。
2. 长度恰为 $2 \times K$ 的括号序列不能放入任何盒子。

请计算满足条件的所有不同放置方法的总数，并输出其除以 $998244353$ 的余数。

在这里，我们认为两种放置方法不同当且仅当在某个盒子中放入的括号序列不同。

输入由以下三个整数给出，代表盒子数量、左括号总数以及禁止的长度：

$N$ $M$ $K$

输出满足条件的放置方法总数对 $998244353$ 取模后的结果。

• $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$ 分。

示例解释

例如，对于以下组合：

• (()) ，空
• ()() ，空
• 空，(())
• 空，()()

共计 $4$ 种不同的放置方法。

本翻译由 AI 自动生成