17424번 - 2xN 타일링과 쿼리

문제

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

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

각 쿼리는 다음과 같다.

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

입력

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

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

출력

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

제한

힌트