Little Cyan Fish は区間の集合について研究しています。
この問題では、区間 $\{x \mid l \le x \le r\}$ を $[l, r]$ と表します。区間 $[l, r]$ を要素に持つ集合 $S$ は、以下の 3 つの条件をすべて満たすとき、かつそのときに限り Cyanic であると呼ばれます：
- $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$。すなわち、$S$ のすべての要素は $[0, n]$ に含まれる整数を端点とする閉区間 $[l, r]$ である。
- すべての整数 $i \in [0, n]$ について、区間 $[i, i] \in S$ である。
- 任意の 2 つの区間 $[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$ に属していなければならない。
理解を助けるため、Little Cyan Fish は $n = 3$ の場合の以下の例を考えました：
- 集合 $\{[0, 0], [2, 2]\}$ は Cyanic 集合ではありません。区間 $[1, 1] \notin S$ であるため、2 番目の条件に違反しています。
- 集合 $\{[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$ となるため、3 番目の条件に違反しています。
- 集合 $\{[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 集合は非常にたくさんあり、Little Cyan Fish はそれらすべてが大好きです。すべての Cyanic 集合からなる集合を $\mathcal{C}$ とします。与えられた整数 $q$ に対して、Little Cyan Fish は次の和を知りたがっています：
$$\sum_{S \in \mathcal{C}} q^{|S|}$$
この和は非常に大きくなる可能性があるため、Little Cyan Fish はこの和を $998\,244\,353$ で割った余りを計算するようあなたに頼みました。
入力
入力の 1 行目には 2 つの整数 $n$ ($1 \le n \le 10^5$) と $q$ ($1 \le q < 998\,244\,353$) が与えられます。
出力
答えを表す 1 つの整数を含む 1 行を出力してください。
入出力例
入力例 1
1 2
出力例 1
12
説明
入力例 1 について：Cyanic 集合は $\{[0, 0], [1, 1]\}$ と $\{[0, 0], [1, 1], [0, 1]\}$ の 2 つがあるため、答えは $2^2 + 2^3 = 12$ です。
入力例 2
3 1
出力例 2
22
入力例 3
10 3
出力例 3
855061512