Description

An $n \times m$ $01$ matrix, in which some positions are already fixed. Positions marked '.' can be filled with $0$ or $1$. Count the number of matrices for which the difference between any two adjacent positions is $1$ (i.e., adjacent cells sharing a side have different values), and output the answer modulo $10007$.

Input Format

The first line contains two integers $n, m$.

Then follows an $n \times m$ matrix consisting of $\verb!0!,\verb!1!,\verb!.!$.

Output Format

Output a single integer: the number of matrices satisfying the condition, modulo $10007$.

2 3
10.
...

5

Hint

Constraints and Conventions

For $100\%$ of the testdata, $n \times m \le 225$.

Translated by ChatGPT 5