在建立了城市并举行了祭典之后，人们将目光投向了隐藏在光流中更深层次的秩序。

他们雕刻出顺应光流路径的形状，并研究这些图案，寻找其中交织的和谐规律。

但他们很快发现，并非所有的图案都能带来和谐。有些图案失去了平衡并崩溃了。

为了重新找到平衡，他们一次又一次地研究并改进他们的设计。

追寻他们留下的排列，重建和谐之光的图案。

岛民们通过在 $N \times N$ 的网格上放置灯来进行实验，试图寻找稳定的配置。从上往下数第 $r$ 行、从左往右数第 $c$ 列的单元格表示为 $(r, c)$。

如果一个配置满足以下条件，则被认为是稳定的（stable）：

• 每行恰好有一盏灯，每列也恰好有一盏灯。
• 不存在不稳定的模式。
  • 当存在三盏灯分别位于 $(r_1, c_1), (r_2, c_2), (r_3, c_3)$，且满足 $r_1 < r_2 < r_3$ 且 $c_1 > c_2 > c_3$ 时，就会出现不稳定模式。

例如，在下图展示的例子中，左侧的配置是稳定的。右侧的配置是不稳定的，因为 $(1, 5), (2, 2), (3, 1)$ 这三个单元格形成了一个不稳定模式。

为了探索更精细的排列，岛民们引入了以下形式的附加限制：

• 在前 $c$ 列（从第 1 列到第 $c$ 列）中，放置的 $c$ 盏灯的最大行索引必须恰好为 $r$。

他们有兴趣观察随着这些限制的添加或删除，稳定配置的数量会如何变化。

输入格式

第一行包含两个空格分隔的整数 $N$ 和 $Q$，分别表示网格的大小和询问的数量。

接下来的 $Q$ 行，每行包含以下格式之一的询问：

• 1 r_i c_i：添加一个新的限制。在第 1 列到第 $c_i$ 列中放置的 $c_i$ 盏灯中，最大行索引必须恰好为 $r_i$。
• 2 x_i：移除在第 $x_i$ 次询问中添加的限制。
• 3：输出满足当前所有生效限制的稳定结构的数量。

你可以假设在询问开始之前没有任何限制。

输出格式

对于每个类型为 3 的询问，输出单行，包含满足当前所有生效限制的稳定结构数量模 $10^9 + 7$ 的结果。

数据范围

设 $t_i$ 表示第 $i$ 次询问的类型。

• $3 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• $1 \le t_i \le 3$ ($1 \le i \le Q$)
• $1 \le r_i \le N$ ($1 \le i \le Q, t_i = 1$)
• $1 \le c_i \le N$ ($1 \le i \le Q, t_i = 1$)
• $1 \le x_i < i$ ($1 \le i \le Q, t_i = 2$)
• $t_{x_i} = 1$ ($1 \le i \le Q, t_i = 2$)
• $x_i \ne x_j$ ($1 \le i < j \le Q, t_i = t_j = 2$)
• 至少存在一个类型为 3 的询问。

子任务

• 子任务 1（4 分）：$N = 3, Q \le 400$
• 子任务 2（7 分）：$N \le 8, Q \le 400$
• 子任务 3（10 分）：$Q = 1$
• 子任务 4（23 分）：$N \le 400, Q \le 400$
• 子任务 5（25 分）：$N \le 2000, Q \le 2000$
• 子任务 6（13 分）：$Q \le 2$
• 子任务 7（18 分）：无附加限制。

样例

输入样例 1

3 8
3
1 1 1
3
2 2
1 3 1
3
1 1 3
3

输出样例 1

5
2
1
0

输入样例 2

5 11
1 4 3
1 5 2
3
2 2
3
1 3 1
1 3 2
1 5 5
3
2 6
3

输出样例 2

0
18
2
6

输入样例 3

20 1
3

输出样例 3

564120378

输入样例 4

20 2
1 15 10
3

输出样例 4

936990054