/ AOCode / 题库 /

Mission 2 - B2 : The Ques of the Guards 2 (MID)

Mission 2 - B2 : The Ques of the Guards 2 (MID)

P1025 Mission 2 - B2 : The Ques of the Guards 2 (MID)

Problem Name: question2mid

Problem Background

After decoding the important message, all the options that the USW is going to do is known. The army that Radar leads is quickly outside the capital of the USW, the WA state.

The President of the USW knows that he is going to lose, so he let the guards open the door. But the guards don’t want to. Only if Radar answers their question right, they will open the door.

So can you help Radar solve the question?

Problem Statement

The Guards need Radar to tell them what’s the \(n^{th}\) element in the Fibonacci Numbers.

Note that we define that \(F_0=0,\ F_1=1\).

Because the number is huge, print the number modulo \(998244353\).

Input

\(n\)

Output

\(F_n\pmod{998244353}\)

Samples

Input 1


Output 1


Constraints

  • \(1 \le n \le 10^{18}\).

信息

ID
1025
难度
1950
分类
数论 | Fibonacci数列矩阵乘法 点击显示
标签
(无)
递交数
65
已通过
7
通过率
11%
上传者

相关

在下列训练计划中:

AOSC Problems

在下列比赛中:

AOCode Round #3 & AOSC #2