Little Cyan Fish is conducting research on a set of intervals.

In this problem, we use $[l, r]$ to denote the interval $\{x \mid l \le x \le r\}$. For a set $S$ containing intervals $[l, r]$, it is said to be Cyanic if and only if the following three conditions hold:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. That is, every element of $S$ is a closed interval $[l, r]$ with integer endpoints contained in $[0, n]$.
2. For all integers $i \in [0, n]$, the interval $[i, i] \in S$.
3. For any two intervals $[l_0, r_0] \in S$ and $[l_1, r_1] \in S$, if $l_0 \le l_1 < r_0 \le r_1$, then the intervals $[l_0, l_1]$ and $[r_0, r_1]$ must also belong to $S$.

To help you understand, Little Cyan Fish considers the following scenarios for $n = 3$.

• The set $\{[0, 0], [2, 2]\}$ is not a Cyanic set. The interval $[1, 1] \notin S$, so the second condition is violated.
• The set $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ is not a Cyanic set. When we choose $[l_0, r_0] = [0, 2]$ and $[l_1, r_1] = [1, 3]$, the interval $[l_0, l_1] = [0, 1] \notin S$, so the third condition is violated.
• The set $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ is a Cyanic set.
• The set $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ is also a Cyanic set.

Of course, there are many, many Cyanic sets, and Little Cyan Fish loves all of them. Let $\mathcal{C}$ be the set of all Cyanic sets. For a given integer $q$, Little Cyan Fish wants to know the sum:

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

As the sum can be huge, Little Cyan Fish asks you to calculate the sum modulo $998\,244\,353$.

Input

The first line of the input contains two integers $n$ ($1 \le n \le 10^5$) and $q$ ($1 \le q < 998\,244\,353$).

Output

Output a single line containing a single integer indicating the answer.

Examples

Input 1

1 2

Output 1

12

Explanation

For Sample 1: There are two Cyanic sets $\{[0, 0], [1, 1]\}$ and $\{[0, 0], [1, 1], [0, 1]\}$, so the answer is $2^2 + 2^3 = 12$.

Input 2

3 1

Output 2

22

Input 3

10 3

Output 3

855061512