No Adjacent Ones Matrix

You are given an $n \times m$ binary matrix. Some positions are already determined as either 0 or 1, and the undetermined positions are denoted by a dot (.). Your task is to count the number of ways to fill in the dots with 0 or 1 such that no two adjacent cells (adjacent vertically or horizontally) are both 1. Since the answer can be very large, output it modulo $10007$.

Constraints

• The first line of the input contains two integers $n$ and $m$.
• The following $n$ lines each contain a string of length $m$ consisting of characters '0', '1', or '.'.

Note: Two cells are considered adjacent if they share a common side.

inputFormat

The first line contains two space-separated integers: $n$ and $m$.

The next $n$ lines each contain a string of length $m$. Each character is either '0', '1' or '.', where '.' indicates an undetermined cell that can be filled with either 0 or 1.

outputFormat

Output a single integer: the number of valid matrices modulo $10007$.

sample

2 2
.1
0.

1