题目背景

原题链接
本题与原题的区别，只有模数和数据范围不同。

题目描述

给定一个正整数 $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$。