Little Cyan Fish está realizando una investigación sobre un conjunto de intervalos.

En este problema, usamos $[l, r]$ para denotar el intervalo $\{x \mid l \le x \le r\}$. Para un conjunto $S$ que contiene intervalos $[l, r]$, se dice que es Ciánico si y solo si se cumplen las siguientes tres condiciones:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Es decir, cada elemento de $S$ es un intervalo cerrado $[l, r]$ con extremos enteros contenido en $[0, n]$.
2. Para todos los enteros $i \in [0, n]$, el intervalo $[i, i] \in S$.
3. Para cualesquiera dos intervalos $[l_0, r_0] \in S$ y $[l_1, r_1] \in S$, si $l_0 \le l_1 < r_0 \le r_1$, entonces los intervalos $[l_0, l_1]$ y $[r_0, r_1]$ también deben pertenecer a $S$.

Para ayudarte a entender, Little Cyan Fish considera los siguientes escenarios para $n = 3$.

• El conjunto $\{[0, 0], [2, 2]\}$ no es un conjunto Ciánico. El intervalo $[1, 1] \notin S$, por lo que se viola la segunda condición.
• El conjunto $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ no es un conjunto Ciánico. Cuando elegimos $[l_0, r_0] = [0, 2]$ y $[l_1, r_1] = [1, 3]$, el intervalo $[l_0, l_1] = [0, 1] \notin S$, por lo que se viola la tercera condición.
• El conjunto $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ es un conjunto Ciánico.
• El conjunto $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ también es un conjunto Ciánico.

Por supuesto, hay muchísimos conjuntos Ciánicos, y a Little Cyan Fish le encantan todos. Sea $\mathcal{C}$ el conjunto de todos los conjuntos Ciánicos. Para un entero dado $q$, Little Cyan Fish quiere conocer la suma:

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

Como la suma puede ser enorme, Little Cyan Fish te pide que calcules la suma módulo $998\,244\,353$.

Entrada

La primera línea de la entrada contiene dos enteros $n$ ($1 \le n \le 10^5$) y $q$ ($1 \le q < 998\,244\,353$).

Salida

Imprime una sola línea que contenga un solo entero indicando la respuesta.

Ejemplos

Entrada 1

1 2

Salida 1

12

Explicación

Para el Ejemplo 1: Hay dos conjuntos Ciánicos $\{[0, 0], [1, 1]\}$ y $\{[0, 0], [1, 1], [0, 1]\}$, por lo que la respuesta es $2^2 + 2^3 = 12$.

Entrada 2

3 1

Salida 2

22

Entrada 3

10 3

Salida 3

855061512