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

В этой задаче мы используем $[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