Problem Description

Your company is going to build offices on an $N \times M$ grid graph. As shown in the figure, the grid graph has horizontal and vertical edges, and all edge weights are $1$.

During the day, all roads can be used. During the night, only $N \times M - 1$ edges are lit and can be used.

You like to patrol the offices. Every day, you start from one office, traverse each office exactly once through available edges in some order, and finally return to the starting point. You want to choose a subset $S$ of vertices on the grid graph such that the length of the shortest route needed for patrolling is the same during the day and during the night.

You need to compute, modulo $10^9+7$, the number of possible $S$ under three different requirements:

1. $|S| \geq 2$.
2. $|S| = 2$.
3. $|S| = 3$.

Input Format

The first line contains three integers $N, M, T$, where $T$ indicates which version of the problem you need to compute.

Then follow $N$ lines, each containing a string $A_{i,j}$ of length $M$.

• $A_{i,j} \in \{\texttt{1}, \texttt{3}\}$ means that $(i,j)$ has an edge to $(i-1,j)$.
• $A_{i,j} \in \{\texttt{2}, \texttt{3}\}$ means that $(i,j)$ has an edge to $(i,j-1)$.

It is guaranteed that the input forms a tree.

Output Format

Output one integer, the answer modulo $10^9+7$.

2 3 2
022
031

12

2 3 3
022
031

10

2 3 1
022
031

25

Hint

[Sample Explanation]

As shown in the figure above.

The following are the valid choices when $|S| = 2$: $\{A,B\}$, $\{A,C\}$, $\{A,E\}$, $\{A,F\}$, $\{B,C\}$, $\{B,D\}$, $\{B,E\}$, $\{B,F\}$, $\{C,D\}$, $\{C,E\}$, $\{C,F\}$, $\{D,E\}$.

The following are the valid choices when $|S| = 3$: $\{A,B,C\}$, $\{A,B,E\}$, $\{A,B,F\}$, $\{A,C,E\}$, $\{A,C,F\}$, $\{B,C,D\}$, $\{B,C,E\}$, $\{B,C,F\}$, $\{B,D,E\}$, $\{C,D,E\}$.

The following are the valid choices when $|S| = 4$: $\{A,B,C,E\}$, $\{A,B,C,F\}$, $\{B,C,D,E\}$.

[Constraints]

This problem uses bundled subtasks.

• Subtask 1 (4 pts): $N, M \leq 2$.
• Subtask 2 (5 pts): $N = 1$.
• Subtask 3 (9 pts): $T = 2$, $N, M \leq 50$.
• Subtask 4 (11 pts): $T = 2$.
• Subtask 5 (9 pts): $T = 3$, $N, M \leq 20$.
• Subtask 6 (13 pts): $T = 3$.
• Subtask 7 (14 pts): $T = 1$, $N, M \leq 4$.
• Subtask 8 (10 pts): $T = 1$, $N, M \leq 50$.
• Subtask 9 (9 pts): $T = 1$, $A_{i,j} \neq \texttt{3}$.
• Subtask 10 (16 pts): $T = 1$.

For $100\%$ of the testdata, it is guaranteed that $1 \leq T \leq 3$, $1 \leq N, M \leq 10^3$, and $A_{i,j} \in \{\texttt{0}, \texttt{1}, \texttt{2}, \texttt{3}\}$.

Translated by ChatGPT 5