Masz do dyspozycji uczciwą monetę (co oznacza, że przy każdym rzucie istnieje 50% szans na orła i 50% szans na reszkę). Chcesz użyć jej do wygenerowania ciągu $n$ liczb całkowitych $a_1, a_2, \dots, a_n$. W tym celu powtórzysz poniższy proces dokładnie $n$ razy:

• Rzucaj monetą, aż uzyskasz wynik reszka.
• Załóżmy, że przed zatrzymaniem uzyskałeś $k$ razy wynik orzeł.
• Liczba całkowita $k$ zostaje wygenerowana i dodana do końca ciągu.

Dla ciągu liczb całkowitych $b_1, b_2, \dots, b_m$, niech $\text{mex}(b_1, b_2, \dots, b_m)$ oznacza najmniejszą nieujemną liczbę całkowitą $x$ taką, że:

• Dla każdego $1 \le i < x$ istnieje $1 \le j \le m$ takie, że $b_j = i$.
• $b_j \neq x$ dla wszystkich $1 \le j \le m$.

Na przykład $\text{mex}(0, 1, 0, 3) = 2$, $\text{mex}(4, 3, 2, 1, 0, 6, 7, 5) = 8$ oraz $\text{mex}(1, 2, 3) = 0$.

Teraz chcesz obliczyć wartość oczekiwaną $\text{mex}(a_1, a_2, \dots, a_n)$ modulo $998\,244\,353$.

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 10^5$).

Wyjście

Wypisz w jednej linii pojedynczą liczbę całkowitą, oznaczającą wynik modulo $998\,244\,353$.

Przykład

Wejście 1

1

Wyjście 1

499122177

Wejście 2

3

Wyjście 2

561512450

Uwagi

W pierwszym przykładzie:

• Jeśli $a_1 = 0$, mamy $\text{mex}(a_1) = 1$. Prawdopodobieństwo tego zdarzenia wynosi $1/2$.
• W przeciwnym razie mamy $\text{mex}(a_1) = 0$.

Zatem odpowiedź wynosi $1 \times \frac{1}{2} + 0 \times (1 - \frac{1}{2}) = \frac{1}{2} \equiv 499122177 \pmod{998\,244\,353}$.