#2101. 这是一道放ak题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: admin

题目描述

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

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

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

输入格式

输入一个整数 表示第 个月

输出格式

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

样例

Input

3

Output

2

Input

114514

Output

855088846

数据范围与提示