Квадраты Фибоначчи

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n이 10^18까지 주어질 때, 피보나치 수 f_0부터 f_n까지의 제곱합을 998244353으로 나눈 나머지를 구한다.

난이도: 보통10점 중 6점
유형: 수학, 동적 계획법, 분할 정복, 정수론
정답자: 아직 제출이 없습니다

문제

Сэму приходится много времени путешествовать пешком, и чтобы немного отвлечься от однообразного занятия, он решает в уме всякие задачки. Сегодня он размышлял над последовательностью чисел Фибоначчи. Она строится по следующему правилу:

$f\_0 = f\_1 = 1$
$f\_i = f\_{i - 2} + f\_{i - 1}$ , для всех $i \ge 2$

Он посчитал значение $\sum\limits\_{i = 0}^{n} f\_i^2$ , и теперь просит вас сделать то же самое, чтобы сравнить ответ. Так как это число может быть большим, посчитайте его по модулю $998\\,244\\,353$ .

입력

В единственной строке дано одно целое число $n$ ( $0 \le n \le 10^{18}$ ).

출력

Выведите одно целое число --- ответ на задачу.

예제3

예제 1
입력
```
0
```
예상 출력
```
1
```
예제 2
입력
```
2
```
예상 출력
```
6
```
예제 3
입력
```
4
```
예상 출력
```
40
```