题目背景

（图片来自 phigros 曲绘，侵删。）

还是来谈点现实的吧。

身边的同学 NOI 拿了 Ag，APIO 捧了杯，省选啥的也比小 $\iiint$ 好。小 $\iiint$ 说，他的时间花在游戏上了。可看看隔壁提前招进高中的，florr 号里都有 Super Ant Egg 了。小 $\iiint$ 说，他网不好，实力发挥不出来。可再看隔壁 i wanna 大神，都开始速通 i wanna be the guy 了。小 $\iiint$ 争道，他也没打多久游戏，只是在专心文化课。但是成绩一拉出来，成了信竞班垫底。小 $\iiint$ 又说，可能是时间花在社交上了吧。大家都觉得他很幽默，因为他在班里一个朋友都没有。

小 $\iiint$ 不明白为什么会这样。

今年对于小 $\iiint$ 来说，可能就是他 OI 生涯的最后一年了。一年太短，能补救多少？能挽回多少？当年他刚学 OI 时，就暗暗地下定决心，要成为大家口中的“神犇”。三年过去，前途仍是一片昏暗。

这或许就是，$\color{#CD0000}\overset{\text{End of a Dream}}{\text{梦\ 的\ 终\ 结}}$。

也许，梦是反着的吧。

……

但是这里是梦熊周赛题目，不是出题人拿来写批话的地方，所以小 $\iiint$ 需要你做一道计数题。

题目描述

给定 $n,q$。现有一个初始为 $0$ 的整数 $m$。你需要支持以下操作：

• 0 x：将 $m$ 加上 $2^x$。
• 1 x：将 $m$ 减去 $2^x$。若 $m<2^x$，则忽略此操作。
• 2：查询有多少长度为 $n$、每个数都在 $1\sim m$ 中的严格递增正整数序列，使得其前缀异或和与后缀异或和均严格递增。答案对 $998\,244\,353$ 取模。

其中，一颗序列 $a_1,a_2,\cdots,a_n$ 的前缀异或和是指序列 $s_1,s_2,\cdots,s_n$，满足 $s_i=\begin{cases}a_1&i=1\\a_{i}\oplus s_{i-1}&i\ge2\end{cases}$，而其后缀异或和是指序列 $t_1,t_2,\cdots,t_n$，满足 $t_i=\begin{cases}a_n&i=1\\a_{n-i+1}\oplus t_{i-1}&i\ge2\end{cases}$，其中 $x\oplus y$ 表示 $x$ 与 $y$ 的按位异或。

输入格式

第一行两个正整数，表示 $n,q$。

接下来 $q$ 行，每行表示一个操作。

输出格式

对于每个 2 操作，输出对应的答案对 $998\,244\,353$ 取模的值。

样例

3 4
0 0
0 1
0 2
2

2

样例 1 解释

查询时 $m=7$，满足要求的序列为 $\{1,2,4\}$ 和 $\{1,3,5\}$，可以证明不存在其他解。

注意，序列 $\{1,3,1\}$ 是不满足要求的，尽管其前、后缀异或和均为严格递增数列 $\{1,2,3\}$，该序列本身并不满足严格递增的限制。

20 15
0 1
0 2
0 21
0 5
2
0 15
1 18
0 7
0 8
0 25
2
1 22
0 12
0 13
2

313288290
39181640
134388812

数据范围

本题开启捆绑测试。

特殊性质 A：仅有最后一次操作为 2 操作。
特殊性质 B：不包含 1 操作。

对于 $100\%$ 的数据，$3\le n\le 10^7$，$1\le q\le 2\times10^5$，$0\le x\le 10^7$。