켄켄 구역 채우기

켄켄(KenKen)은 2004년 일본에서 나온 논리 퍼즐이다. 퍼즐은 $n \times n$ 격자를 서로 겹치지 않는 구역으로 나눈 것이고, 구역마다 정수 목표값과 산술 연산자가 하나씩 붙는다. 격자 전체를 1 이상 $n$ 이하의 수로 채우되 다음 두 규칙을 지켜야 한다.

• 같은 행이나 같은 열에 같은 수가 두 번 나오지 않는다
• 각 구역에서는 그 구역에 적힌 수와 그 구역의 연산자로 목표값을 만들어야 한다

이 문제는 퍼즐 전체가 아니라 구역 하나만 다룬다. 아래 그림은 $8 \times 8$ 퍼즐에서 잘라낸 구역 두 개와 각 구역을 채우는 방법 몇 가지를 보여 준다.

연산자별 조건은 다음과 같다.

• +: 구역에 적힌 수의 합이 $t$이다
• *: 구역에 적힌 수의 곱이 $t$이다
• -: 구역은 정확히 두 칸으로 이루어지고, 큰 수에서 작은 수를 뺀 값이 $t$이다
• /: 구역은 정확히 두 칸으로 이루어지고, 큰 수를 작은 수로 나눈 값이 나머지 없이 $t$이다

구역 밖의 칸은 따지지 않는다. 다만 구역 안에서 같은 행이나 같은 열에 놓인 두 칸은 서로 다른 수를 가져야 한다. 어느 한 칸이라도 수가 다르면 다른 채우기로 센다.

그림의 첫 번째 구역을 $9 \times 9$ 퍼즐에 놓으면 9와 2를 쓰는 채우기가 두 가지 더 생긴다. 두 번째 구역의 첫 번째 채우기에서는 윗줄의 1과 4를 맞바꿀 수 없다. 맞바꾸면 같은 열에 1이 두 번 들어가기 때문이다.

첫 줄에 $n$, $m$, $t$, op가 주어진다. $n$은 구역이 속한 퍼즐의 크기, $m$은 구역에 든 칸의 개수, $t$는 목표값이고, op는 +, -, *, / 중 하나이다.

이어서 구역에 든 칸의 위치 $m$개가 행 번호 $r$과 열 번호 $c$의 쌍으로 주어진다. 위치는 한 줄에 이어질 수도 있고 여러 줄에 나뉠 수도 있다.

한 구역의 칸은 모두 이어져 있다. 즉 구역의 어느 칸에서 출발해도 변을 맞댄 칸을 따라 구역의 나머지 칸에 모두 닿는다.

$4 \le n \le 9$, $2 \le m \le 10$, $0 < t$, $1 \le r, c \le n$이다.

주어진 크기의 켄켄 퍼즐에서 그 구역을 채우는 방법의 수를 출력한다.