Квадраты Фибоначчи
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Входные данные

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

Выходные данные

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

Примеры

Входные данные
0
Выходные данные
1
Входные данные
2
Выходные данные
6
Входные данные
4
Выходные данные
40