Statement is not available in English language
5. Жизнь пешки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компьютер записывает «биографию» белой шахматной пешки в течение партии на доске $$$8 \times 8$$$.

Начальное положение пешки — клетка E2.

На каждом ходе пешка может остаться на месте, сдвинуться вперед на одну клетку или на две клетки, если это ее первый ход.

Компьютер в начале игры и после каждого хода белых записывает позицию пешки по вертикали. Если пешка была «взята», запись позиции прекращается. Считать, что пешку могут взять сразу после первого хода. При этом пешка не может двигаться вперёд с позиции E8, но может стоять на этой позиции сколько угодно ходов до конца партии.

Вам дана длина шахматной партии, найдите количество всех возможных «жизненных путей» пешки по модулю $$$998244353$$$.

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

Единственная строка входных данных содержит целое число $$$N$$$ ($$$1 \le N \le 10^6$$$) — длину партии.

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

В ответе выведите искомое количество различных шахматных путей по модулю $$$998244353$$$.

Примеры
Входные данные
2
Выходные данные
10
Входные данные
99
Выходные данные
582018135
Примечание

$$$10$$$ возможных путей, если партия длилась два хода: $$$22$$$, $$$23$$$, $$$24$$$, $$$222$$$, $$$223$$$, $$$224$$$, $$$233$$$, $$$234$$$, $$$244$$$, $$$245$$$.