안정적인 구조

도시와 의식이 자리를 잡은 후, 사람들은 빛의 흐름 속에서 더 깊은 질서를 찾고자 했다.

그들은 빛을 따라 형상을 새기고 무늬를 관찰하며 그 안에 담긴 조화의 규칙을 헤아리려 했다.

그러나 얼마 지나지 않아, 그들은 모든 무늬가 조화를 이룰 수 있는 것은 아니라는 사실을 깨달았다. 일부 배열은 균형을 잃고 무너졌고, 사람들은 조화를 이루는 형상을 찾기 위해 고민을 거듭했다.

그들이 남긴 배열을 되짚고, 조화로운 빛의 무늬를 다시 그려보아라.

사람들은 $N\times N$ 크기의 격자 위에 빛을 하나씩 배치하며, 안정적인 무늬를 이루는 방법을 연구했다. 위에서부터 $r$번째 행, 왼쪽에서부터 $c$번째 열의 격자칸을 $(r,c)$로 표기한다.

다음 조건을 만족하는 배치를 안정적인 구조라 부른다.

격자의 각 행과 각 열에 정확히 하나의 빛이 존재해야 한다.
불안정한 배열이 존재하지 않는다.
- 세 빛 $(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)$이 불안정한 배열을 이루므로, 안정적인 구조가 아니다.

사람들은 더 정교한 구조를 탐구하기 위해 다음과 같은 형태의 조건들을 제시했다.

사람들은 이러한 형태의 조건을 추가하거나 제거하며 안정적인 구조의 수가 어떻게 달라지는지 살펴보고자 한다.

첫 줄에 격자의 크기를 나타내는 정수 $N$과 쿼리의 수 $Q$가 공백으로 구분되어 주어진다.

이후 $Q$개의 줄에 걸쳐, 그중 $i$번째 줄에는 다음과 같은 형태 중 하나의 쿼리가 주어진다.

$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$번 쿼리의 종류를 의미한다.