KenKen You Do It?

KenKen is a logic puzzle that appeared in Japan in 2004. A puzzle is an $n \times n$ grid cut into sections that do not overlap, and each section carries an integer target together with one arithmetic operator. You fill the whole grid with numbers from 1 to $n$ so that both rules hold:

• no number appears twice in the same row or in the same column
• in every section the numbers of that section reach the target of the section under the operator of the section

This problem looks at a single section, not at a whole puzzle. The figure shows two sections taken from an $8 \times 8$ puzzle, each with some of the ways its squares can be filled.

The operator decides what the numbers of the section must satisfy:

• +: the numbers add up to $t$
• *: the numbers multiply to $t$
• -: the section has exactly two squares, and the larger number minus the smaller one is $t$
• /: the section has exactly two squares, and the larger number divided by the smaller one is $t$ with no remainder

Squares outside the section do not matter. Two squares of the section that lie in the same row, or in the same column, still have to hold different numbers. Two fillings are different when some square holds a different number.

Placed in a $9 \times 9$ puzzle, the first section of the figure gains two more fillings, the ones that use 9 and 2. In the first filling of the second section you cannot swap the 1 and the 4 of the top row, because that puts two 1s in the same column.

The first line contains $n$, $m$, $t$ and op. Here $n$ is the size of the puzzle that holds the section, $m$ is the number of squares in the section, $t$ is the target value, and op is one of +, -, *, /.

After that come $m$ grid positions, each written as a row number $r$ and a column number $c$. The positions take up one or more lines.

The squares of a section are connected: from any square of the section you reach every other square of the section by crossing shared edges between squares.

The values satisfy $4 \le n \le 9$, $2 \le m \le 10$, $0 < t$ and $1 \le r, c \le n$.

Print the number of ways the section can be filled in a KenKen puzzle of the given size.