题目描述

斐波那契数列定义如下：

• $F_1 = 1$
• $F_2 = 1$
• $F_n = F_{n-1} + F_{n-2}$（$n \ge 3$）

给定一个正整数 $n$，请你计算斐波那契数列的第 $n$ 项对 $9997$ 取模的结果。

输入格式

一行，一个正整数 $n$。

输出格式

一行，一个整数，表示 $F_n \bmod 9997$ 的值。

样例

样例输入

10

样例输出

55

数据范围与提示

• $1 \le n \le 1000$
• 模数为 $9997$，结果为非负整数。