Tray Bien

앙드레 클로드 마르지팡은 프랑스 식당 르 쇼 시앵의 총주방장이다. 그가 쓰는 제빵 팬은 1피트 × 1피트와 1피트 × 2피트, 두 가지 크기뿐이고 개수는 아주 많다. 팬은 깊이가 항상 3피트이고 길이는 제각각인 선반에 넣어 둔다. 예를 들어 길이가 5피트인 선반이라면 아래 두 가지처럼 넣을 수 있다.

그림 G.1

물론 방법은 이 둘 말고도 훨씬 많다. 앙드레는 정리에 유난히 까다로워서 팬의 변을 항상 선반의 두 변과 나란히 맞추고, 팬의 모서리를 선반의 어느 변에서든 정수 피트만큼 떨어뜨리며, 팬이 선반 밖으로 조금이라도 나가지 않게 놓는다. 그래서 길이가 $m$피트인 선반은 한 변이 1피트인 정사각형 칸이 3행 $m$열로 놓인 격자가 되고, 팬 하나는 칸 하나를 덮거나 변을 맞댄 칸 두 개를 덮는다.

문제를 복잡하게 만드는 것은 선반 위에서 물이 새거나 표면이 파인 자리처럼 팬을 올리고 싶지 않은 지점이 있다는 점이다. 그런 지점이 들어 있는 칸은 비워 두어야 하고, 나머지 칸은 모두 정확히 한 개의 팬이 덮어야 한다. 크기가 같은 팬끼리는 구별하지 않으므로, 어떤 칸 두 개를 하나의 1 × 2 팬으로 짝지었는지가 다르면 서로 다른 배치다.

앙드레는 요리에는 능해도 세는 데는 서툴다. 선반에 팬을 놓는 방법의 수를 구하라.

첫째 줄에 정수 $m$과 $n$이 주어진다. $m$($1 \le m \le 24$)은 선반의 길이이고, 선반의 깊이는 항상 3피트다. $n$은 선반 위 불량 지점의 개수다.

둘째 줄에 팬을 올리면 안 되는 지점의 좌표가 $x\ y$ 순서로 $n$개 주어진다. 모든 좌표는 $0 < x < m$과 $0 < y < 3$을 만족하고, 정수인 좌표는 없으며, 소수점 아래 둘째 자리까지 주어진다. $n = 0$이면 둘째 줄은 비어 있다.

선반에 팬을 놓는 방법의 수를 한 줄에 출력한다. 답은 부호 있는 64비트 정수 범위에 들어간다.