Little Cyan Fish forscht über eine Menge von Intervallen.

In diesem Problem verwenden wir $[l, r]$, um das Intervall $\{x \mid l \le x \le r\}$ zu bezeichnen. Eine Menge $S$, die Intervalle $[l, r]$ enthält, heißt genau dann Cyanisch, wenn die folgenden drei Bedingungen erfüllt sind:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Das heißt, jedes Element von $S$ ist ein abgeschlossenes Intervall $[l, r]$ mit ganzzahligen Endpunkten, das in $[0, n]$ enthalten ist.
2. Für alle ganzen Zahlen $i \in [0, n]$ gilt $[i, i] \in S$.
3. Für je zwei Intervalle $[l_0, r_0] \in S$ und $[l_1, r_1] \in S$ gilt: Wenn $l_0 \le l_1 < r_0 \le r_1$, dann müssen auch die Intervalle $[l_0, l_1]$ und $[r_0, r_1]$ zu $S$ gehören.

Zum besseren Verständnis betrachtet Little Cyan Fish die folgenden Szenarien für $n = 3$.

• Die Menge $\{[0, 0], [2, 2]\}$ ist keine Cyanische Menge. Das Intervall $[1, 1] \notin S$, sodass die zweite Bedingung verletzt ist.
• Die Menge $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ ist keine Cyanische Menge. Wenn wir $[l_0, r_0] = [0, 2]$ und $[l_1, r_1] = [1, 3]$ wählen, gilt $[l_0, l_1] = [0, 1] \notin S$, sodass die dritte Bedingung verletzt ist.
• Die Menge $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ ist eine Cyanische Menge.
• Die Menge $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ ist ebenfalls eine Cyanische Menge.

Natürlich gibt es sehr, sehr viele Cyanische Mengen, und Little Cyan Fish liebt sie alle. Sei $\mathcal{C}$ die Menge aller Cyanischen Mengen. Für eine gegebene ganze Zahl $q$ möchte Little Cyan Fish die folgende Summe wissen:

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

Da die Summe riesig sein kann, bittet Little Cyan Fish Sie, die Summe modulo $998\,244\,353$ zu berechnen.

Eingabe

Die erste Zeile der Eingabe enthält zwei ganze Zahlen $n$ ($1 \le n \le 10^5$) und $q$ ($1 \le q < 998\,244\,353$).

Ausgabe

Geben Sie eine einzige Zeile mit einer einzigen ganzen Zahl aus, die die Antwort angibt.

Beispiele

Eingabe 1

1 2

Ausgabe 1

12

Erklärung

Zu Beispiel 1: Es gibt zwei Cyanische Mengen $\{[0, 0], [1, 1]\}$ und $\{[0, 0], [1, 1], [0, 1]\}$, also lautet die Antwort $2^2 + 2^3 = 12$.

Eingabe 2

3 1

Ausgabe 2

22

Eingabe 3

10 3

Ausgabe 3

855061512