#P9942. 斐波那契数列

斐波那契数列

题目描述

在斐波那契数列中,F0=0,F1=1,Fn=Fn−1+Fn−2(n>1)F_0 = 0 , F_1 = 1 , F_n = F_{n−1} + F_{n−2} (n>1) 。

给定整数 n n,求 Fn% 998244353 F_n \% \ 998244353。

输入格式

包含一个整数 n(0≤n≤1018) n(0\le n \le 10^{18})。

输出格式

一个整数表示结果。

样例

输入样例

5

输出样例

5