P3160 [CQOI2012] Local Minima

There is an $n$ by $m$ integer matrix in which each integer between $1$ and $n \times m$ appears exactly once. If a cell is smaller than all of its adjacent cells (adjacent means sharing a side or a vertex), we say this cell is a local minimum. Given the positions of all local minima, your task is to determine how many matrices are possible. Output the answer modulo $12{,}345{,}678$.

The first line contains two integers $n$ and $m$, the number of rows and columns. Each of the next $n$ lines contains $m$ characters. For each $i$ from $1$ to $n$, the $ (i + 1) $-th line’s $j$-th character represents whether the cell at row $i$ and column $j$ is a local minimum. Each character is either `X` or `.`, where `X` denotes a local minimum and `.` denotes a non-local minimum.

Output a single line containing the number of possible matrices modulo $12{,}345{,}678$.

- Constraints - For $100\%$ of the testdata, $1 \le n \le 4$, $1 \le m \le 7$. Translated by ChatGPT 5