M. 近似递增序列
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

对于一个长度为 $$$m\ (m\ge 1)$$$ 的整数序列 $$$a_1,a_2,\cdots,a_m\ (a_i \gt 0)$$$，如果最多只存在一个整数 $$$p\ (1\le p \lt m)$$$ 满足 $$$a_p\ge a_{p+1}$$$，则可以称这样的序列为近似递增序列，同时我们定义这个近似递增序列的权值为 $$$\prod_{i=1}^m a_i$$$。

设 $$$f(i)$$$ 表示权值为 $$$i$$$ 的近似递增序列的数量，duoluoluo 想知道 $$$\sum_{i=1}^n f(i)$$$ 的值，但是他连 $$$f(2)$$$ 都不会计算，你可以帮帮他吗？由于答案可能会非常大，你只需要求出其对 $$$998\,244\,353$$$ 取模后的值。

Input

一行包含一个整数 $$$n\ (1\le n\le 10^8)$$$，其含义如题目所述。

Output

输出一个整数，表示 $$$\sum_{i=1}^n f(i)$$$ 对 $$$998\,244\,353$$$ 取模后的值。

Examples
Input
2
Output
7
Input
5
Output
26
Note

样例一中 $$$7$$$ 个近似递增序列为：$$$\{1\}$$$，$$$\{1,1\}$$$，$$$\{1,1,2\}$$$，$$$\{1,2\}$$$，$$$\{1,2,1\}$$$，$$$\{2\}$$$，$$$\{2,1\}$$$。