Маленька Ціанова Рибка проводить дослідження множини відрізків.

У цій задачі ми використовуємо $[l, r]$ для позначення відрізка $\{x \mid l \le x \le r\}$. Множина $S$, що містить відрізки $[l, r]$, називається ціановою (Cyanic) тоді й лише тоді, коли виконуються такі три умови:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Тобто кожен елемент $S$ є замкненим відрізком $[l, r]$ із цілочисельними кінцями, що міститься в $[0, n]$.
2. Для всіх цілих чисел $i \in [0, n]$ відрізок $[i, i] \in S$.
3. Для будь-яких двох відрізків $[l_0, r_0] \in S$ та $[l_1, r_1] \in S$, якщо $l_0 \le l_1 < r_0 \le r_1$, то відрізки $[l_0, l_1]$ та $[r_0, r_1]$ також повинні належати $S$.

Щоб допомогти вам зрозуміти, Маленька Ціанова Рибка розглядає такі приклади для $n = 3$.

• Множина $\{[0, 0], [2, 2]\}$ не є ціановою множиною. Відрізок $[1, 1] \notin S$, тому друга умова порушується.
• Множина $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ не є ціановою множиною. Коли ми вибираємо $[l_0, r_0] = [0, 2]$ та $[l_1, r_1] = [1, 3]$, відрізок $[l_0, l_1] = [0, 1] \notin S$, тому третя умова порушується.
• Множина $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ є ціановою множиною.
• Множина $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ також є ціановою множиною.

Звісно, існує дуже-дуже багато ціанових множин, і Маленька Ціанова Рибка любить їх усі. Нехай $\mathcal{C}$ — множина всіх ціанових множин. Для заданого цілого числа $q$ Маленька Ціанова Рибка хоче дізнатися суму:

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

Оскільки ця сума може бути величезною, Маленька Ціанова Рибка просить вас обчислити її за модулем $998\,244\,353$.

Вхідні дані

Перший рядок вхідних даних містить два цілі числа $n$ ($1 \le n \le 10^5$) та $q$ ($1 \le q < 998\,244\,353$).

Вихідні дані

Виведіть один рядок, що містить одне ціле число — відповідь на задачу.

Приклади

Вхідні дані 1

1 2

Вихідні дані 1

12

Пояснення

Для прикладу 1: Існує дві ціанові множини $\{[0, 0], [1, 1]\}$ та $\{[0, 0], [1, 1], [0, 1]\}$, тому відповідь дорівнює $2^2 + 2^3 = 12$.

Вхідні дані 2

3 1

Вихідні дані 2

22

Вхідні дані 3

10 3

Вихідні дані 3

855061512