Little Cyan Fish tutkii välien joukkoa.

Tässä tehtävässä merkitsemme merkinnällä $[l, r]$ väliä $\{x \mid l \le x \le r\}$. Välejä $[l, r]$ sisältävää joukkoa $S$ kutsutaan syaaniseksi (Cyanic), jos ja vain jos seuraavat kolme ehtoa pätevät:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Toisin sanoen jokainen joukon $S$ alkio on suljettu väli $[l, r]$, jonka päätepisteet ovat välillä $[0, n]$ olevia kokonaislukuja.
2. Kaikilla kokonaisluvuilla $i \in [0, n]$ väli $[i, i] \in S$.
3. Mille tahansa kahdelle välille $[l_0, r_0] \in S$ ja $[l_1, r_1] \in S$, jos $l_0 \le l_1 < r_0 \le r_1$, niin myös välien $[l_0, l_1]$ ja $[r_0, r_1]$ täytyy kuulua joukkoon $S$.

Auttaakseen sinua ymmärtämään Little Cyan Fish tarkastelee seuraavia tapauksia arvolla $n = 3$.

• Joukko $\{[0, 0], [2, 2]\}$ ei ole syaaninen joukko. Väli $[1, 1] \notin S$, joten toinen ehto rikkoutuu.
• Joukko $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ ei ole syaaninen joukko. Kun valitsemme $[l_0, r_0] = [0, 2]$ ja $[l_1, r_1] = [1, 3]$, väli $[l_0, l_1] = [0, 1] \notin S$, joten kolmas ehto rikkoutuu.
• Joukko $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ on syaaninen joukko.
• Joukko $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ on myös syaaninen joukko.

Syaanisia joukkoja on tietenkin hyvin, hyvin monta, ja Little Cyan Fish pitää niistä kaikista. Olkoon $\mathcal{C}$ kaikkien syaanisten joukkojen joukko. Annetulle kokonaisluvulle $q$ Little Cyan Fish haluaa tietää summan:

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

Koska summa voi olla valtava, Little Cyan Fish pyytää sinua laskemaan summan modulo $998\,244\,353$.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ($1 \le n \le 10^5$) ja $q$ ($1 \le q < 998\,244\,353$).

Tuloste

Tulosta yksi rivi, joka sisältää yhden vastausta ilmaisevan kokonaisluvun.

Esimerkit

Syöte 1

1 2

Tuloste 1

12

Selitys

Esimerkille 1: On olemassa kaksi syaanista joukkoa $\{[0, 0], [1, 1]\}$ ja $\{[0, 0], [1, 1], [0, 1]\}$, joten vastaus on $2^2 + 2^3 = 12$.

Syöte 2

3 1

Tuloste 2

22

Syöte 3

10 3

Tuloste 3

855061512