A nihilistic scorpion is going to cross a river because it kinda just felt like doing it man. There are n altruistic frogs swimming in the river, forming a linear bridge for the other animals. The scorpion can not swim, so it is going to jump on the frogs. As the scorpion lands on a frog it stings the next frog in front of it. The frog that was stung quickly drowns.

The scorpion doesn't need to sting the frogs, nor does it even need to jump on them - it could just cross the river in one jump; but it stings the frogs anyway, because that's just the way scorpions are bro.

It is too lazy to make jumps backwards, but still has the energy to ponder the question: "In how many ways could I cross the river?". The scorpion didn't bother to learn math in school, so it orders you to calculate that number modulo 998244353.

Formally, after landing on frog i the scorpion can jump on any of the frogs i+2, i+3,\dots,n or the opposite side of the river. On the first jump it can land on any of the frogs or the opposite side.

Input

The only line of input contains the number of frogs, n.

Output

Output the number of ways the scorpion can cross the river modulo 998244353.

Constraints

• 1 \leq n \leq 10^5

Example 1

Input:

1

Output:

2

Explanation:

The routes for the scorpion are (1, x) and (x)

Example 3

Input:

3

Output:

5

Explanation

The routes are (1, 3, x), (1, x), (2, x), (3, x), (x)

Example 3

Input:

1000

Output:

506723686