Counting Nearly Increasing Sequences by Weight

Consider an integer sequence (a_1,a_2,\cdots,a_m) of length (m) (with (m\ge1)) where every (a_i) is a positive integer. The sequence is called a "nearly increasing sequence" if there exists at most one index (p) with (1\le p<m) such that (a_p\ge a_{p+1}). In other words, all adjacent pairs are in strictly increasing order except for at most one pair.

We define the weight of the sequence to be (\prod_{i=1}^{m}a_i). Let (f(i)) denote the number of nearly increasing sequences whose weight is exactly (i). For a given positive integer (n), compute [ S(n)=\sum_{i=1}^{n}f(i) \pmod{998,244,353}. ]

For example, when (n=1), the only possible sequence is either [1] or [1,1] (note that [1,1,1] is not allowed since it has two positions (p) where (a_p\ge a_{p+1})). Therefore, (S(1)=2).

inputFormat

The input consists of a single integer (n) ((1\le n)) on a single line.

outputFormat

Output one integer (S(n)), the total number of nearly increasing sequences whose weight is at most (n) (when weights are exactly counted) modulo (998,244,353).

sample

1

2