Background

Original link: https://oier.team/problems/X3H。

---

(The picture is from the Phigros song illustration. Please contact for removal if infringed.)

Let us talk about something real.

Classmates around Xiao $\iiint$ got Ag in NOI, won awards in APIO, and did better than Xiao $\iiint$ in NOI Qualifier and such. Xiao $\iiint$ said he spent his time on games. But look at the neighbor who was admitted to high school early—there is already a Super Ant Egg in their florr account. Xiao $\iiint$ said his internet was bad, so he could not perform well. But look again at the i wanna masters next door—they have already started speedrunning i wanna be the guy. Xiao $\iiint$ argued that he had not played games for long, and he was focusing on academic subjects. But when grades came out, he became the bottom of the competitive programming class. Xiao $\iiint$ then said maybe he spent time socializing. Everyone thought he was funny, because he did not have a single friend in the class.

Xiao $\iiint$ did not understand why it turned out like this.

This year, for Xiao $\iiint$, might be the last year of his OI career. One year is too short—how much can be fixed? how much can be saved? When he first learned OI, he secretly made up his mind to become a "legendary top contestant" in everyone's eyes. Three years passed, and the future was still completely dark.

This might be $\color{#CD0000}\overset{\text{End of a Dream}}{\text{the end of a dream}}$.

Maybe, dreams run in reverse.

...

But this is a Dream Bear weekly contest problem, not a place for the problemsetter to write nonsense, so Xiao $\iiint$ needs you to solve a counting problem.

Problem Description

Given $n, q$. There is an integer $m$ initially equal to $0$. You need to support the following operations:

• 0 x: add $2^x$ to $m$.
• 1 x: subtract $2^x$ from $m$. If $m < 2^x$, ignore this operation.
• 2: query how many strictly increasing positive integer sequences of length $n$, where each number is in $1 \sim m$, satisfy that both the prefix XOR sums and the suffix XOR sums are strictly increasing. Output the answer modulo $998\,244\,353$.

Here, for a sequence $a_1, a_2, \cdots, a_n$, its prefix XOR sums refer to a sequence $s_1, s_2, \cdots, s_n$, where

$$s_i=\begin{cases} a_1&i=1\\ a_{i}\oplus s_{i-1}&i\ge2 \end{cases}$$

and its suffix XOR sums refer to a sequence $t_1, t_2, \cdots, t_n$, where

$$t_i=\begin{cases} a_n&i=1\\ a_{n-i+1}\oplus t_{i-1}&i\ge2 \end{cases}$$

where $x \oplus y$ denotes the bitwise XOR of $x$ and $y$.

Input Format

The first line contains two positive integers, denoting $n, q$.

The next $q$ lines each describe one operation.

Output Format

For each 2 operation, output the corresponding answer modulo $998\,244\,353$.

3 4
0 0
0 1
0 2
2

2

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

Hint

Sample Explanation #1

When querying, $m = 7$. The sequences that satisfy the requirements are $\{1,2,4\}$ and $\{1,3,5\}$. It can be proven that no other solutions exist.

Note that the sequence $\{1,3,1\}$ does not satisfy the requirements. Although both its prefix and suffix XOR sums are strictly increasing sequences $\{1,2,3\}$, the sequence itself does not satisfy the strictly increasing constraint.

Constraints

This problem uses bundled testdata.

Subtask	Score	$n\le$	$q\le$	$x\le$	Special property
$1$	$5$		$10$
$2$	$10$	$10^3$	$10^3$
$3$	$11$		$2\times10^5$	$10^5$	AB
$4$	$14$	$10^5$
$5$	$16$	$10^7$	$10^2$	$10^7$	B
$6$	$19$		$2\times10^5$
$7$	$25$

Special property A: only the last operation is a 2 operation.
Special property B: does not contain 1 operations.

For $100\%$ of the data, $3 \le n \le 10^7$, $1 \le q \le 2\times 10^5$, $0 \le x \le 10^7$.

Translated by ChatGPT 5