Background

Original problem link.
The only differences between this problem and the original one are the modulus and the constraints.

Problem Description

Given a positive integer $n$, ask how many strings of length $n$ satisfy that the string is a “program fragment”.

The exact definition is as follows:

A single semicolon ; is a “statement”.

The empty string is a “program fragment”.

If string A is a “program fragment” and string B is a “statement”, then AB is a “program fragment”.

If string A is a “program fragment”, then {A} is a “statement block”.

If string A is a “statement block”, then A is a “statement”, and []A and []()A are both “functions”.

If string A is a “function”, then (A) is a “function”, and A and A() are “values”.

If string A is a “value”, then (A) is a “value”, and A; is a “statement”.

Note: A being B does not mean B is A.

Input Format

Input one line with one positive integer $n$.

Output Format

Output one line with one integer representing the answer. As a kind problem setter, you only need to take it modulo $998244353$.

4

9

7

140

8923

424180943

114514

552971057

Hint

[Sample 1 Explanation]
Valid “program fragments” include: ;;;;, ;;{}, ;{;}, ;{};, {;;}, {;};, {{}}, {};;, {}{}.

[Constraints]
For $30\%$ of the testdata, $1 \le n \le 10^5$.
For $100\%$ of the testdata, $1 \le n \le 10^7$.

Translated by ChatGPT 5