У вас есть честная монета (это означает, что при подбрасывании монеты вероятность выпадения орла составляет 50%, а решки — 50%). Вы хотите использовать её для генерации последовательности из $n$ целых чисел $a_1, a_2, \dots, a_n$. Для этого вы повторяете следующий процесс ровно $n$ раз:

• Подбрасывайте монету до тех пор, пока не выпадет решка.
• Предположим, что до остановки выпало $k$ орлов.
• Целое число $k$ добавляется в конец последовательности.

Для последовательности целых чисел $b_1, b_2, \dots, b_m$ обозначим через $\text{mex}(b_1, b_2, \dots, b_m)$ наименьшее неотрицательное целое число $x$ такое, что:

• Для каждого $1 \le i < x$ существует $1 \le j \le m$ такое, что $b_j = i$.
• $b_j \neq x$ для всех $1 \le j \le m$.

Например, $\text{mex}(0, 1, 0, 3) = 2$, $\text{mex}(4, 3, 2, 1, 0, 6, 7, 5) = 8$ и $\text{mex}(1, 2, 3) = 0$.

Теперь вам нужно вычислить математическое ожидание $\text{mex}(a_1, a_2, \dots, a_n)$ по модулю $998\,244\,353$.

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

Первая строка входных данных содержит единственное целое число $n$ ($1 \le n \le 10^5$).

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

Выведите единственное целое число, представляющее ответ по модулю $998\,244\,353$.

Примеры

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

1

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

499122177

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

3

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

561512450

Примечание

В первом примере:

• Если $a_1 = 0$, то $\text{mex}(a_1) = 1$. Вероятность этого события равна $1/2$.
• В противном случае $\text{mex}(a_1) = 0$.

Таким образом, ответ равен $1 \times \frac{1}{2} + 0 \times (1 - \frac{1}{2}) = \frac{1}{2} \equiv 499122177 \pmod{998\,244\,353}$.