Little Cyan Fish는 구간들의 집합에 대해 연구하고 있습니다.

이 문제에서는 구간 $\{x \mid l \le x \le r\}$를 $[l, 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$에 속해야 합니다.

이해를 돕기 위해, Little Cyan Fish는 $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 집합이 존재하며, Little Cyan Fish는 그 모든 집합을 좋아합니다. 모든 Cyanic 집합들의 집합을 $\mathcal{C}$라고 합시다. 주어진 정수 $q$에 대해, Little Cyan Fish는 다음 합을 알고 싶어 합니다:

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

이 합은 매우 클 수 있으므로, Little Cyan Fish는 여러분에게 이 합을 $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