Tri-Color Puzzle

Tri-Color Puzzle은 한 변에 $S$개의 셀이 놓이는 육각형 셀을 삼각형 모양으로 배열한 퍼즐이며, 셀의 총개수는 $N = \frac{S(S+1)}{2}$이다. 예를 들어 아래는 한 변이 4이고 셀이 10개인 퍼즐이다.

퍼즐을 풀려면 모든 셀을 빨강, 초록, 파랑 중 하나로 칠해야 한다. 위에 셀 하나, 아래에 셀 두 개가 놓인 세 셀의 각 묶음에서, 세 셀의 색이 모두 같거나 세 셀의 색이 모두 달라야 한다. 설명을 분명하게 하려고 색과 함께 빗금 무늬도 사용한다.

빨강 = 초록 = 파랑 =

어떤 퍼즐은 일부 셀의 색이 미리 정해져 있고, 나머지 셀은 위의 규칙에 따라 채운다. 아래 예시의 해는 3개이다.

아래 예시에는 해가 없다.

아래 예시의 해는 정확히 1개이다.

입력으로 Tri-Color Puzzle의 내용을 받아, 그 퍼즐의 해의 개수를 출력하는 프로그램을 작성하라.

첫 줄에는 공백으로 구분된 10진수 정수 $S$와 $I$가 주어진다 ($3 \le S \le 19$, $0 \le I \le N = \frac{S(S+1)}{2}$). 첫 줄 다음에는 $I$개의 줄이 이어지며, 각 줄에는 행 번호 $r$, 그 행에서 셀의 위치 $c$, 초기 색 하나의 색 코드 $cc$가 10진수 정수 세 개로 주어진다 ($1 \le r \le S$, $1 \le c \le r$, $0 \le cc \le 2$). 코드 0은 빨강, 1은 초록, 2는 파랑을 뜻한다.

입력으로 주어진 Tri-Color Puzzle의 해의 개수를 한 줄에 출력한다.