A nihilistic scorpion is crossing a river. There are n altruistic frogs swimming in the river, forming a linear bridge for other animals. The scorpion cannot 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.

The scorpion is too lazy to make backward jumps, but it 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 asks 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 to the opposite side of the river. On the first jump, it can land on any of the frogs or on 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), where x denotes reaching the other side.

Example 2

Input:

3

Output:

5

Explanation: The routes are (1, 3, x), (1, x), (2, x), (3, x), (x).

Example 3

Input:

1000

Output:

506723686