Little Cyan Fish mène des recherches sur un ensemble d'intervalles.

Dans ce problème, nous utilisons $[l, r]$ pour désigner l'intervalle $\{x \mid l \le x \le r\}$. Un ensemble $S$ contenant des intervalles $[l, r]$ est dit Cyanique si et seulement si les trois conditions suivantes sont vérifiées :

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Autrement dit, chaque élément de $S$ est un intervalle fermé $[l, r]$ à extrémités entières contenu dans $[0, n]$.
2. Pour tout entier $i \in [0, n]$, l'intervalle $[i, i] \in S$.
3. Pour toute paire d'intervalles $[l_0, r_0] \in S$ et $[l_1, r_1] \in S$, si $l_0 \le l_1 < r_0 \le r_1$, alors les intervalles $[l_0, l_1]$ et $[r_0, r_1]$ doivent également appartenir à $S$.

Pour vous aider à comprendre, Little Cyan Fish considère les scénarios suivants pour $n = 3$.

• L'ensemble $\{[0, 0], [2, 2]\}$ n'est pas un ensemble Cyanique. L'intervalle $[1, 1] \notin S$, donc la deuxième condition est violée.
• L'ensemble $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ n'est pas un ensemble Cyanique. Lorsque l'on choisit $[l_0, r_0] = [0, 2]$ et $[l_1, r_1] = [1, 3]$, l'intervalle $[l_0, l_1] = [0, 1] \notin S$, donc la troisième condition est violée.
• L'ensemble $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ est un ensemble Cyanique.
• L'ensemble $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ est également un ensemble Cyanique.

Bien sûr, il existe énormément d'ensembles Cyaniques, et Little Cyan Fish les aime tous. Soit $\mathcal{C}$ l'ensemble de tous les ensembles Cyaniques. Pour un entier $q$ donné, Little Cyan Fish veut connaître la somme :

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

Comme cette somme peut être immense, Little Cyan Fish vous demande de la calculer modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient deux entiers $n$ ($1 \le n \le 10^5$) et $q$ ($1 \le q < 998\,244\,353$).

Sortie

Affichez une seule ligne contenant un seul entier indiquant la réponse.

Exemples

Entrée 1

1 2

Sortie 1

12

Explication

Pour l'exemple 1 : Il y a deux ensembles Cyaniques $\{[0, 0], [1, 1]\}$ et $\{[0, 0], [1, 1], [0, 1]\}$, donc la réponse est $2^2 + 2^3 = 12$.

Entrée 2

3 1

Sortie 2

22

Entrée 3

10 3

Sortie 3

855061512