타일 깔기

정보기술 연구소의 보수 공사 중, 건설 노동자들은 연구소 복도의 손상된 바닥 타일을 교체해야 한다. 복도의 크기는 2 × n 미터이다. 노동자들에게는 1 × 2 미터와 1 × 1 미터 두 가지 크기의 타일이 무한히 주어진다. 1 × 2 미터 타일은 깔기 전에 90도 회전시킬 수 있으며, 복도를 따라 또는 복도를 가로질러 놓을 수 있다.

노동자들은 이미 공사를 시작하여 복도의 일부 위치에 1 × 1 크기의 타일 k개를 깔았다. 공사를 마치려면 현장 감독이 남은 작업 계획을 세워야 한다. 이를 위해 감독은 아직 타일이 깔리지 않은 자리에 타일을 어떻게 놓을지 결정해야 한다. 방법은 여러 가지가 있을 수 있으며, 감독은 모든 경우를 검토하여 가장 좋은 방법을 고르려 한다. 그 전에 감독은 검토해야 할 경우의 수가 몇 가지인지 알고 싶어 한다. 이 수를 109 + 7로 나눈 나머지를 구해야 한다.

복도의 길이 n과 이미 깔린 타일의 위치가 주어질 때, 남은 자리에 타일을 깔는 방법의 수를 구하는 프로그램을 작성해야 한다. 답은 109 + 7로 나눈 나머지로 출력한다.

입력 파일의 첫 번째 줄에는 두 정수 n과 k가 주어진다. n은 복도의 길이이고, k는 이미 깔린 단위 타일의 개수이다 (1 ≤ n ≤ 100 000, 0 ≤ k < 2n).

다음 k개 줄에는 각각 두 정수 xi와 yi가 주어진다. 이는 이미 깔린 단위 타일의 위치를 나타내며, i번째 타일은 복도의 xi번째 미터, yi번째 줄에 깔려 있다 (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

출력 파일에는 복도에 타일을 깔는 방법의 수를 109 + 7로 나눈 나머지 하나를 정수로 출력한다.

그림 1. 첫 번째 예제에서 타일을 깔는 모든 방법

그림 2. 세 번째 예제에서 타일을 깔는 모든 방법. 이미 깔린 타일은 회색으로 표시되어 있다.