촬영

시간 제한: 1000 ms. 메모리 제한: 1024 MB. 베를란디아 챔피언십 결승전까지 며칠밖에 남지 않았다. 모든 일을 막판에 몰아서 하다 보니 경기 촬영을 포함한 몇 가지 운영 사항이 아직 정리되지 않았다. 도시에는 촬영을 맡겠다는 회사가 여러 곳 있지만, 이 회사들은 서로 경쟁 중이어서 경쟁사의 촬영 기사가 아니라 자기 회사의 카메라로 경기를 찍기를 원한다. 촬영 기사는 경기장 관중석에 배치할 수 있다. 관중석은 $n$개의 줄로 이루어져 있고, 첫 번째 줄에는 $2n-1$개의 좌석, 두 번째 줄에는 $2n-3$개의 좌석이 있으며, 이렇게 줄마다 2개씩 줄어들어 $n$번째 줄에는 1개의 좌석이 있다. 다만 모든 관객이 경기를 가볍게 여기는 것은 아니어서, 일부 좌석은 이미 표가 팔렸다. 촬영 기사는 비어 있는 좌석에만 배치할 수 있다. 경기장 예시. 회색 좌석은 촬영 기사가 찍는 좌석이다. 검은 좌석은 관객이 차지한 좌석이다. 엑스 표시는 촬영 기사이며, 각 기사의 카메라가 찍는 좌석도 함께 표시했다. 하지만 경쟁이 항상 벌어지는 것은 아니다. 모든 촬영 기사는 같은 모델의 카메라를 쓰며, 이 카메라는 화각이 고정되어 있어 바로 다음 줄의 좌석 3개, 한 줄 건너뛴 줄의 좌석 5개 등을 촬영할 수 있다. 시 당국은 경기를 최고 수준으로 촬영하고 싶어 하며, 가장 좋은 배치를 고를 수 있도록 가능한 배치 방법을 모두 제출하라고 요청했다. 그러나 경기장 운영 측은 이런 방법이 매우 많다고 보고 이 계획에 찬성하지 않는다. 배치 방법이 몇 가지인지 구하라.

첫 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le n \le 2000$, $0 \le m \le 1000$). $n$은 줄의 수이고, $m$은 점유된 좌석의 수이다. 이어서 $m$개의 줄에 점유된 좌석이 한 줄에 하나씩 주어진다. 각 좌석은 두 정수 $r$과 $p$로 주어진다 ($1 \le r \le n$, $1 \le p \le 2(n-r) + 1$). $r$은 줄 번호, $p$는 그 줄 안의 좌석 번호이다.

배치 방법의 수를 $10^9+7$로 나눈 나머지를 출력한다.