시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB2981005324.883%

문제

2xN 크기의 직사각형에 1x2 또는 2x1크기의 타일로 채우는 방법의 수를 구하는 문제는 잘 알려져 있다.

최초에 아무런 제한이 없는 2xN 직사각형에 블럭을 놓는 칸에 대한 제한이 빈번히 생기고 사라질 때 제한을 제외한 나머지 칸을 전부 채우는 방법의 수를 구하는 프로그램을 작성하시오.

각 쿼리는 다음과 같다.

  • 1 x y : (x,y)의 위치에 블럭을 놓을 수 없다는 제한을 추가한다. 이전에 제한이 없었음이 보장된다.
  • 2 x y : (x,y)의 위치에 블럭을 놓을 수 없다는 제한을 삭제한다. 이전에 제한이 있었음이 보장된다.

입력

첫째줄에 N과 쿼리의 수를 나타내는 정수 Q가 공백으로 구분하여 주어진다. (1 ≤ N ≤ 105​​​​, 1 ≤ Q ≤ 2 x 105)

둘째줄부터 Q줄에 걸쳐 2가지 종류의 쿼리가 주어진다. 각 쿼리는 t x y꼴로 주어지며 1 ≤ t, x ≤ 2, 1 ≤ y ≤ N을 만족한다.

출력

Q개의 줄에 걸쳐 i번째 쿼리까지 적용했을 때의 경우의 수를 (109 + 7)로 나눈 나머지를 순서대로 출력한다.

예제 입력 1

5 6
1 1 2
1 1 3
1 2 1
2 1 2
1 1 5
2 1 3

예제 출력 1

0
2
0
2
0
1

출처

  • 문제를 만든 사람: Lawali