Little Cyan Fish กำลังทำวิจัยเกี่ยวกับเซตของช่วง

ในปัญหานี้ เราใช้ $[l, r]$ แทนช่วง $\{x \mid l \le x \le r\}$ สำหรับเซต $S$ ที่ประกอบด้วยช่วง $[l, r]$ จะถูกเรียกว่า Cyanic ก็ต่อเมื่อเป็นไปตามเงื่อนไขทั้งสามข้อต่อไปนี้:

1. $S \subseteq \{[l, r] \mid l, r \in \mathbb{Z}, 0 \le l \le r \le n\}$ นั่นคือ สมาชิกทุกตัวของ $S$ เป็นช่วงปิด $[l, r]$ ที่มีจุดปลายเป็นจำนวนเต็มและอยู่ภายใน $[0, n]$
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 ก็ชอบเซตเหล่านั้นทั้งหมด ให้ $\mathcal{C}$ เป็นเซตของเซต Cyanic ทั้งหมด สำหรับจำนวนเต็ม $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