Помогите с задачей по программированию, пожалуйста. Срочно.

По времени: 1сек
По памяти: 256мб

Условие

Компьюте.р записывает "биографию" белой шахматной пешки в течение партии.

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

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

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

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

Например, если партия длилась два хода, все возможные пути

22
23
24
222
223
224
233
234
244
245
Всего 10 возможных путей.

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

Единственная строка входных данных содержит целое число N (1≤N≤106) - длину партии.

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

Для примера:

Ввод Результат
2 10

99 582018135