Little Cyan Fish đang thực hiện nghiên cứu về một tập hợp các đoạn.
Trong bài toán này, chúng ta dùng $[l, r]$ để ký hiệu đoạn $\{x \mid l \le x \le r\}$. Đối với một tập hợp $S$ chứa các đoạn $[l, r]$, nó được gọi là Cyanic khi và chỉ khi thỏa mãn cả ba điều kiện sau:
- $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$. Nghĩa là, mọi phần tử của $S$ đều là một đoạn đóng $[l, r]$ có hai đầu mút nguyên nằm trong $[0, n]$.
- Với mọi số nguyên $i \in [0, n]$, đoạn $[i, i] \in S$.
- Với hai đoạn bất kỳ $[l_0, r_0] \in S$ và $[l_1, r_1] \in S$, nếu $l_0 \le l_1 < r_0 \le r_1$, thì các đoạn $[l_0, l_1]$ và $[r_0, r_1]$ cũng phải thuộc $S$.
Để giúp bạn dễ hiểu, Little Cyan Fish xét các trường hợp sau với $n = 3$.
- Tập hợp $\{[0, 0], [2, 2]\}$ không phải là tập hợp Cyanic. Đoạn $[1, 1] \notin S$, nên điều kiện thứ hai bị vi phạm.
- Tập hợp $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ không phải là tập hợp Cyanic. Khi ta chọn $[l_0, r_0] = [0, 2]$ và $[l_1, r_1] = [1, 3]$, đoạn $[l_0, l_1] = [0, 1] \notin S$, nên điều kiện thứ ba bị vi phạm.
- Tập hợp $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [0, 1], [1, 2]\}$ là một tập hợp Cyanic.
- Tập hợp $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ cũng là một tập hợp Cyanic.
Tất nhiên, có rất nhiều tập hợp Cyanic, và Little Cyan Fish yêu thích tất cả chúng. Gọi $\mathcal{C}$ là tập hợp tất cả các tập hợp Cyanic. Với một số nguyên $q$ cho trước, Little Cyan Fish muốn biết tổng:
$$\sum_{S \in \mathcal{C}} q^{|S|}$$
Vì tổng này có thể rất lớn, Little Cyan Fish nhờ bạn tính tổng này theo modulo $998\,244\,353$.
Dữ liệu vào
Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n$ ($1 \le n \le 10^5$) và $q$ ($1 \le q < 998\,244\,353$).
Kết quả
In ra một dòng duy nhất chứa một số nguyên duy nhất cho biết kết quả.
Ví dụ
Dữ liệu vào 1
1 2
Kết quả 1
12
Giải thích
Đối với Ví dụ 1: Có hai tập hợp Cyanic là $\{[0, 0], [1, 1]\}$ và $\{[0, 0], [1, 1], [0, 1]\}$, vì vậy đáp án là $2^2 + 2^3 = 12$.
Dữ liệu vào 2
3 1
Kết quả 2
22
Dữ liệu vào 3
10 3
Kết quả 3
855061512