Problem Description

For an integer sequence $a_1,a_2,\cdots,a_m$ of length $m\ (m\ge 1)$ with $a_i>0$, if there exists at most one integer $p\ (1\le p<m)$ such that $a_p\ge a_{p+1}$, then this sequence is called an approximate increasing sequence. We define the weight of such an approximate increasing sequence as $\prod_{i=1}^m a_i$.

Let $f(i)$ denote the number of approximate increasing sequences whose weight is $i$. duoluoluo wants to know the value of $\sum_{i=1}^n f(i)$, but he cannot even compute $f(2)$. Can you help him? Since the answer may be very large, you only need to output it modulo $998\,244\,353$.

Input Format

One line contains an integer $n\ (1\le n\le 10^8)$, whose meaning is as described in the statement.

Output Format

Output one integer, representing $\sum_{i=1}^n f(i)$ modulo $998\,244\,353$.

2

7

5

26

Hint

In sample 1, the $7$ approximate increasing sequences are: $\{1\}$, $\{1,1\}$, $\{1,1,2\}$, $\{1,2\}$, $\{1,2,1\}$, $\{2\}$, $\{2,1\}$.

Translated by ChatGPT 5