안정적인 구조

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

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

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

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

사람들은 $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)$이 불안정한 배열을 이루므로, 안정적인 구조가 아니다.

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

• $1$열부터 $c$열까지 배치된 $c$개 빛의 행 번호 중 최댓값이 $r$이어야 한다.

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

첫 줄에 격자의 크기를 나타내는 정수 $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$번 쿼리의 종류를 의미한다.

• $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\neq x\_j$ $(1\le i\<j\le Q,t\_i=t\_j=2)$
• $3$번 종류의 쿼리가 하나 이상 존재한다.