Little Cyan Fish sta conducendo una ricerca su un insieme di intervalli.

In questo problema, usiamo $[l, r]$ per indicare l'intervallo $\{x \mid l \le x \le r\}$. Un insieme $S$ contenente intervalli $[l, r]$ è detto Cianico se e solo se valgono le seguenti tre condizioni:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Cioè, ogni elemento di $S$ è un intervallo chiuso $[l, r]$ con estremi interi contenuto in $[0, n]$.
2. Per tutti gli interi $i \in [0, n]$, l'intervallo $[i, i] \in S$.
3. Per ogni coppia di intervalli $[l_0, r_0] \in S$ e $[l_1, r_1] \in S$, se $l_0 \le l_1 < r_0 \le r_1$, allora anche gli intervalli $[l_0, l_1]$ e $[r_0, r_1]$ devono appartenere a $S$.

Per aiutarti a capire, Little Cyan Fish considera i seguenti scenari per $n = 3$.

• L'insieme $\{[0, 0], [2, 2]\}$ non è un insieme Cianico. L'intervallo $[1, 1] \notin S$, quindi la seconda condizione è violata.
• L'insieme $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ non è un insieme Cianico. Quando scegliamo $[l_0, r_0] = [0, 2]$ e $[l_1, r_1] = [1, 3]$, l'intervallo $[l_0, l_1] = [0, 1] \notin S$, quindi la terza condizione è violata.
• L'insieme $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ è un insieme Cianico.
• L'insieme $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ è anch'esso un insieme Cianico.

Naturalmente esistono moltissimi insiemi Cianici, e Little Cyan Fish li adora tutti. Sia $\mathcal{C}$ l'insieme di tutti gli insiemi Cianici. Per un dato intero $q$, Little Cyan Fish vuole conoscere la somma:

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

Poiché la somma può essere enorme, Little Cyan Fish ti chiede di calcolarla modulo $998\,244\,353$.

Input

La prima riga dell'input contiene due interi $n$ ($1 \le n \le 10^5$) e $q$ ($1 \le q < 998\,244\,353$).

Output

Stampa una singola riga contenente un singolo intero che indica la risposta.

Esempi

Input 1

1 2

Output 1

12

Spiegazione

Per l'Esempio 1: Ci sono due insiemi Cianici $\{[0, 0], [1, 1]\}$ e $\{[0, 0], [1, 1], [0, 1]\}$, quindi la risposta è $2^2 + 2^3 = 12$.

Input 2

3 1

Output 2

22

Input 3

10 3

Output 3

855061512