Description

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$.

Input Format

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 Format

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

3 2
X.
..
.X

60

Hint

• Constraints
  • For $100\%$ of the testdata, $1 \le n \le 4$, $1 \le m \le 7$.

Translated by ChatGPT 5