You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

传说中，有一只神奇的兔子，它有着特殊的繁殖规律。

• 在第1个月，只有1对兔子。
• 在第2个月，还是只有1对兔子。
• 从第3个月开始，每个月的兔子总对数等于前两个月兔子总对数之和。

给定一个整数 $n$，请你计算在第 $n$ 个月时，总共有多少对兔子,并对998244353取模。

Input Format

输入一个整数 $n$ 表示第 $n$ 个月

Output Format

输出一个整数，表示第 $n$ 个月时兔子的数量。

Sample

Input$1$

3

Output$1$

2

Input$2$

114514

Output$2$

855088846

Hint

$1 \le n \le 1e6$