2xN 타일링과 쿼리
시간 제한2초메모리 제한256 MB
1x2와 2x1 타일로 2xN 격자를 채우는 경우의 수를 구하되, 쿼리마다 특정 칸이 사용 금지되거나 해제될 때마다 다시 계산한다.
문제
2xN 크기의 직사각형을 1x2 또는 2x1 크기의 타일로 채우는 방법의 수를 구하는 문제는 잘 알려져 있다.
최초에 아무런 제한이 없는 2xN 직사각형에서 블럭을 놓을 수 없는 칸에 대한 제한이 생기고 사라지기를 반복할 때, 제한된 칸을 제외한 나머지 칸을 전부 채우는 방법의 수를 구하는 프로그램을 작성하시오.
각 쿼리는 다음과 같다.
- 1 x y : (x,y)의 위치에 블럭을 놓을 수 없다는 제한을 추가한다. 이전에 제한이 없었음이 보장된다.
- 2 x y : (x,y)의 위치에 블럭을 놓을 수 없다는 제한을 삭제한다. 이전에 제한이 있었음이 보장된다.
입력
첫째 줄에 N과 쿼리의 수를 나타내는 정수 Q가 공백으로 구분하여 주어진다. (1 ≤ N ≤ 10^5, 1 ≤ Q ≤ 2 x 10^5)
둘째 줄부터 Q줄에 걸쳐 2가지 종류의 쿼리가 주어진다. 각 쿼리는 t x y 꼴로 주어지며 1 ≤ t, x ≤ 2, 1 ≤ y ≤ N을 만족한다.
출력
Q개의 줄에 걸쳐 i번째 쿼리까지 적용했을 때의 경우의 수를 (10^9 + 7)로 나눈 나머지를 순서대로 출력한다.