小青鱼正在对区间集合进行研究。

在本题中，我们用 $[l, r]$ 表示区间 $\{x \mid l \le x \le r\}$。对于一个包含区间 $[l, r]$ 的集合 $S$，当且仅当满足以下三个条件时，称其为 Cyanic 集合：

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$。即 $S$ 中的每个元素都是端点为整数且包含在 $[0, n]$ 内的闭区间 $[l, r]$。
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]\}$ 不是 Cyanic 集合。区间 $[1, 1] \notin S$，因此违反了第二个条件。
• 集合 $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ 不是 Cyanic 集合。当我们选择 $[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]\}$ 是一个 Cyanic 集合。
• 集合 $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ 也是一个 Cyanic 集合。

当然，存在非常非常多的 Cyanic 集合，小青鱼喜欢它们所有。设 $\mathcal{C}$ 为所有 Cyanic 集合构成的集合。对于给定的整数 $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：存在两个 Cyanic 集合 $\{[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