Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×
C. Подсчет бинарных строк (опять)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Напомним, что бинарная строка — это строка, состоящая из символов 0 и/или 1. Подстрокой бинарной строки назовем её непрерывную подпоследовательность.

Предположим, у вас есть бинарная строка $$$s$$$. Вы можете проводить с ней следующую последовательность операций:

  • во время первой операции вы можете либо не делать ничего, либо выбрать в $$$s$$$ любую подстроку длины $$$1$$$ из нулей и удалить её;
  • во время второй операции вы можете либо не делать ничего, либо выбрать в $$$s$$$ любую подстроку длины $$$2$$$ из нулей и удалить её;
  • во время третьей операции вы можете либо не делать ничего, либо выбрать в $$$s$$$ любую подстроку длины $$$4$$$ из нулей и удалить её;
  • и так далее (во время $$$i$$$-й операции выбирается подстрока длины $$$2^{i-1}$$$).

После каждого удаления получившиеся части строки склеиваются в том же порядке. Операции можно завершить в любой момент (в том числе можно оставить строку без изменений).

Назовем бинарную строку красивой, если из неё такой последовательностью операций можно удалить все нули. Например:

  • 000 — красивая строка: 000 $$$\rightarrow$$$ 00 $$$\rightarrow$$$ $$$\varepsilon$$$ (за $$$\varepsilon$$$ обозначается пустая строка);
  • 10100000000100 — красивая строка: 10100000000100 $$$\rightarrow$$$ 1100000000100 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 11000000001 $$$\rightarrow$$$ 111;
  • 111 — красивая строка, в ней уже нет нулей;
  • 010100 не является красивой строкой.

Ваша задача — посчитать количество красивых бинарных строк длины $$$n$$$.

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

В единственной строке задано одно целое число $$$n$$$ ($$$2 \le n \le 2\,000\,000$$$).

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

Выведите одно целое число — количество красивых бинарных строк длины $$$n$$$, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
2
Выходные данные
4
Входные данные
3
Выходные данные
7
Входные данные
4
Выходные данные
13
Входные данные
13
Выходные данные
724
Входные данные
42
Выходные данные
1346030
Входные данные
1234567
Выходные данные
163685965
Примечание

Для $$$n=2$$$ все бинарные строки красивые.

Для $$$n=3$$$ все бинарные строки, кроме 010, являются красивыми.