Little Cyan Fish prowadzi badania nad zbiorem przedziałów.

W tym zadaniu używamy oznaczenia $[l, r]$ dla przedziału $\{x \mid l \le x \le r\}$. Zbiór $S$ zawierający przedziały $[l, r]$ nazywamy Cyjanowym wtedy i tylko wtedy, gdy spełnione są następujące trzy warunki:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Oznacza to, że każdy element zbioru $S$ jest przedziałem domkniętym $[l, r]$ o całkowitych końcach, zawartym w $[0, n]$.
2. Dla wszystkich liczb całkowitych $i \in [0, n]$ przedział $[i, i] \in S$.
3. Dla dowolnych dwóch przedziałów $[l_0, r_0] \in S$ oraz $[l_1, r_1] \in S$, jeśli $l_0 \le l_1 < r_0 \le r_1$, to przedziały $[l_0, l_1]$ oraz $[r_0, r_1]$ również muszą należeć do $S$.

Aby ułatwić Ci zrozumienie, Little Cyan Fish rozważa następujące przypadki dla $n = 3$.

• Zbiór $\{[0, 0], [2, 2]\}$ nie jest zbiorem Cyjanowym. Przedział $[1, 1] \notin S$, więc drugi warunek jest naruszony.
• Zbiór $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ nie jest zbiorem Cyjanowym. Gdy wybierzemy $[l_0, r_0] = [0, 2]$ oraz $[l_1, r_1] = [1, 3]$, przedział $[l_0, l_1] = [0, 1] \notin S$, więc trzeci warunek jest naruszony.
• Zbiór $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ jest zbiorem Cyjanowym.
• Zbiór $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ również jest zbiorem Cyjanowym.

Oczywiście istnieje bardzo, bardzo wiele zbiorów Cyjanowych, a Little Cyan Fish kocha je wszystkie. Niech $\mathcal{C}$ będzie rodziną wszystkich zbiorów Cyjanowych. Dla danej liczby całkowitej $q$ Little Cyan Fish chce poznać sumę:

$$\sum_{S \in \mathcal{C}} q^{|S|}$$

Ponieważ suma ta może być ogromna, Little Cyan Fish prosi Cię o obliczenie jej modulo $998\,244\,353$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ ($1 \le n \le 10^5$) oraz $q$ ($1 \le q < 998\,244\,353$).

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę całkowitą oznaczającą odpowiedź.

Przykłady

Wejście 1

1 2

Wyjście 1

12

Wyjaśnienie

Dla przykładu 1: Istnieją dwa zbiory Cyjanowe $\{[0, 0], [1, 1]\}$ oraz $\{[0, 0], [1, 1], [0, 1]\}$, więc odpowiedź wynosi $2^2 + 2^3 = 12$.

Wejście 2

3 1

Wyjście 2

22

Wejście 3

10 3

Wyjście 3

855061512