Litli blágræni fiskurinn (Little Cyan Fish) stundar rannsóknir á mengi bila.

Í þessu verkefni notum við $[l, r]$ til að tákna bilið $\{x \mid l \le x \le r\}$. Fyrir mengi $S$ sem inniheldur bil $[l, r]$ er sagt að það sé Cyanic ef og aðeins ef eftirfarandi þrjú skilyrði gilda:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Það er, hvert stak í $S$ er lokað bil $[l, r]$ með heiltöluendapunktum sem liggja í $[0, n]$.
2. Fyrir allar heiltölur $i \in [0, n]$ gildir að bilið $[i, i] \in S$.
3. Fyrir sérhver tvö bil $[l_0, r_0] \in S$ og $[l_1, r_1] \in S$, ef $l_0 \le l_1 < r_0 \le r_1$, þá verða bilin $[l_0, l_1]$ og $[r_0, r_1]$ einnig að tilheyra $S$.

Til að hjálpa þér að skilja skoðar Litli blágræni fiskurinn eftirfarandi dæmi fyrir $n = 3$.

• Mengið $\{[0, 0], [2, 2]\}$ er ekki Cyanic mengi. Bilið $[1, 1] \notin S$, þannig að annað skilyrðið er brotið.
• Mengið $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ er ekki Cyanic mengi. Þegar við veljum $[l_0, r_0] = [0, 2]$ og $[l_1, r_1] = [1, 3]$, þá er bilið $[l_0, l_1] = [0, 1] \notin S$, þannig að þriðja skilyrðið er brotið.
• Mengið $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ er Cyanic mengi.
• Mengið $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ er einnig Cyanic mengi.

Auðvitað eru til mjög, mjög mörg Cyanic mengi, og Litli blágræni fiskurinn elskar þau öll. Látum $\mathcal{C}$ vera mengi allra Cyanic mengja. Fyrir gefna heiltölu $q$ vill Litli blágræni fiskurinn vita summuna:

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

Þar sem summan getur verið risastór biður Litli blágræni fiskurinn þig um að reikna summuna módúló $998\,244\,353$.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur $n$ ($1 \le n \le 10^5$) og $q$ ($1 \le q < 998\,244\,353$).

Úttak

Prentið eina línu sem inniheldur eina heiltölu sem gefur til kynna svarið.

Dæmi

Inntak 1

1 2

Úttak 1

12

Skýring

Fyrir dæmi 1: Það eru tvö Cyanic mengi $\{[0, 0], [1, 1]\}$ og $\{[0, 0], [1, 1], [0, 1]\}$, þannig að svarið er $2^2 + 2^3 = 12$.

Inntak 2

3 1

Úttak 2

22

Inntak 3

10 3

Úttak 3

855061512