Problem Description

There is a binary tree. The root node contains an empty string. For each node, the string on its left child is the string of its parent with one left parenthesis appended at the end, and the string on its right child is the string of its parent with one right parenthesis appended at the end. Each leaf node in the tree corresponds one-to-one to a valid bracket sequence consisting of $n$ pairs of parentheses.

Given $n$, find the number of edges in a maximum matching of this tree.

Input Format

The input consists of one line containing an integer $n$.

Output Format

Output one line containing an integer, representing the number of sequences that satisfy the condition. The answer may be very large, so output the remainder when divided by $998244353$.

9

10350

Hint

[Test Case Scale and Assumptions]

• For $20\%$ of the test cases, $n \leq 10$.
• For $40\%$ of the test cases, $n \leq 300$.
• For $60\%$ of the test cases, $n \leq 5000$.
• For $85\%$ of the test cases, $n \leq 10^5$.
• For all test cases, $1 \leq n \leq 10^6$.

Lanqiao Cup 2022 National Contest Group A, Problem J.

Translated by ChatGPT 5