直接自然溢出啥事没有 加强版

[原题链接](https://www.luogu.com.cn/problem/P6103) 本题与原题的区别，只有模数和数据范围不同。 

给定一个正整数 $n$，问有多少个长度为 $n$ 的字符串，满足这个字符串是一个「程序片段」。 具体定义如下： 单个分号 `;` 是一个「语句」。 空串 是一个「程序片段」。 如果字符串 `A` 是「程序片段」，字符串 `B` 是「语句」，则 `AB` 是「程序片段」。 如果字符串 `A` 是「程序片段」，则 `{A}` 是「语句块」。 如果字符串 `A` 是「语句块」，则 `A` 是「语句」，`[]A` 和 `[]()A` 都是「函数」。 如果字符串 `A` 是「函数」，则 `(A)` 是「函数」，`A` 和 `A()` 都是「值」。 如果字符串 `A` 是「值」，则 `(A)` 是「值」，`A;` 是「语句」。 **注意：`A` 是 `B` 并不代表 `B` 是 `A`。**

输入一行一个正整数 $n$。

输出一行一个整数表示答案，作为良心出题人，你只需要对 $998244353$ 取模。

4

9

7

140

8923

424180943

114514

552971057

【样例一解释】 合法的「程序片段」有：`;;;;`，`;;{}`，`;{;}`，`;{};`，`{;;}`，`{;};`，`{{}}`，`{};;`，`{}{}`。 【数据范围】 对于 $30\%$ 的数据，$1\le n \le 10^5$； 对于 $100\%$ 的数据，$1\le n \le 10^7$。