הדג הציאני הקטן (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$.

כדי לעזור לכם להבין, הדג הציאני הקטן בוחן את התרחישים הבאים עבור $n = 3$.

• הקבוצה $\{[0, 0], [2, 2]\}$ אינה קבוצה ציאנית. הקטע $[1, 1] \notin S$, ולכן התנאי השני מופר.
• הקבוצה $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 2], [1, 3]\}$ אינה קבוצה ציאנית. כאשר אנו בוחרים $[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]\}$ היא קבוצה ציאנית.
• הקבוצה $\{[0, 0], [1, 1], [2, 2], [3, 3], [0, 3], [1, 2]\}$ היא גם קבוצה ציאנית.

כמובן, ישנן קבוצות ציאניות רבות מאוד, והדג הציאני הקטן אוהב את כולן. תהא $\mathcal{C}$ קבוצת כל הקבוצות הציאניות. עבור מספר שלם נתון $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: ישנן שתי קבוצות ציאניות $\{[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