Кішкентай Циан Балығы кесінділер жиынына зерттеу жүргізіп жатыр.

Бұл есепте біз $\{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$ жиынына тиісті болуы керек.

Түсінуге оңай болуы үшін, Кішкентай Циан Балығы $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