Little Cyan Fish sedang melakukan penelitian tentang suatu himpunan interval.

Pada masalah ini, kita menggunakan $[l, r]$ untuk menyatakan interval $\{x \mid l \le x \le r\}$. Untuk suatu himpunan $S$ yang berisi interval-interval $[l, r]$, himpunan tersebut dikatakan Cyanic jika dan hanya jika ketiga kondisi berikut terpenuhi:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Artinya, setiap elemen dari $S$ adalah interval tertutup $[l, r]$ dengan titik-titik ujung bilangan bulat yang termuat dalam $[0, n]$.
2. Untuk semua bilangan bulat $i \in [0, n]$, interval $[i, i] \in S$.
3. Untuk setiap dua interval $[l_0, r_0] \in S$ dan $[l_1, r_1] \in S$, jika $l_0 \le l_1 < r_0 \le r_1$, maka interval $[l_0, l_1]$ dan $[r_0, r_1]$ juga harus menjadi anggota $S$.

Untuk membantu Anda memahami, Little Cyan Fish mempertimbangkan skenario berikut untuk $n = 3$.

• Himpunan $\{[0, 0], [2, 2]\}$ bukan himpunan Cyanic. Interval $[1, 1] \notin S$, sehingga kondisi kedua dilanggar.
• Himpunan $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ bukan himpunan Cyanic. Ketika kita memilih $[l_0, r_0] = [0, 2]$ dan $[l_1, r_1] = [1, 3]$, interval $[l_0, l_1] = [0, 1] \notin S$, sehingga kondisi ketiga dilanggar.
• Himpunan $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ adalah himpunan Cyanic.
• Himpunan $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ juga merupakan himpunan Cyanic.

Tentu saja, ada sangat banyak himpunan Cyanic, dan Little Cyan Fish menyukai semuanya. Misalkan $\mathcal{C}$ adalah himpunan dari semua himpunan Cyanic. Untuk suatu bilangan bulat $q$ yang diberikan, Little Cyan Fish ingin mengetahui nilai penjumlahan:

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

Karena hasil penjumlahannya bisa sangat besar, Little Cyan Fish meminta Anda untuk menghitung penjumlahan tersebut modulo $998\,244\,353$.

Masukan

Baris pertama masukan berisi dua bilangan bulat $n$ ($1 \le n \le 10^5$) dan $q$ ($1 \le q < 998\,244\,353$).

Keluaran

Keluarkan satu baris yang berisi satu bilangan bulat yang menyatakan jawabannya.

Contoh

Masukan 1

1 2

Keluaran 1

12

Penjelasan

Untuk Contoh 1: Terdapat dua himpunan Cyanic yaitu $\{[0, 0], [1, 1]\}$ dan $\{[0, 0], [1, 1], [0, 1]\}$, sehingga jawabannya adalah $2^2 + 2^3 = 12$.

Masukan 2

3 1

Keluaran 2

22

Masukan 3

10 3

Keluaran 3

855061512