P6112 Direct Natural Overflow Causes Nothing (Enhanced Version).

[Original problem link](https://www.luogu.com.cn/problem/P6103). The only differences between this problem and the original one are the modulus and the constraints. 

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 one line with one positive integer $n$.

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

[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