P1026 Mission 2 - B3 : The Ques of the Guards 3 (HARD)

Problem Name: question2hard

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 sum of the first \(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

• For \(20\) points:
  • \(1 \le n \le 200000\).
• For another \(40\) points:
  • \(1 \le n \le 10^{9}\).
• For \(100\) points:
  • \(1 \le n \le 10^{18}\).