题目描述

有一棵二叉树，根结点上有一个空字符串，每个点的左儿子上的字符串为其父亲结点的字符串尾部额外加一个左括号，右儿子则是在尾部加一个右括号。树中的每个叶子结点上的字符串都分别和每个由 $n$ 对括号组成的合法括号序列一一对应。

给定 $n$，求此时这棵树的最大匹配所含的边数。

输入格式

输入一行包含一个整数 $n$。

输出格式

输出一行包含一个整数表示满足条件的序列的数量，答案可能很大，请输出答案除以 $998244353$ 的余数。

9

10350

提示

【评测用例规模与约定】

• 对于 $20\%$ 的评测用例，$n \leq 10$；
• 对于 $40\%$ 的评测用例，$n \leq 300$；
• 对于 $60\%$ 的评测用例，$n \leq 5000$；
• 对于 $85\%$ 的评测用例，$n \leq 10^5$；
• 对于所有评测用例，$1 \leq n \leq 10^6$。

蓝桥杯 2022 国赛 A 组 J 题。