Компьютер записывает «биографию» белой шахматной пешки в течение партии на доске $$$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$$$.
