Description

Your company is planning to open its offices in a city with $N$ horizontal and $M$ vertical streets with a building at each intersection. Each building is connected to all of its neighbors by up to two vertical and two horizontal roads, each with a length of $1$.

At night, only $N \times M - 1$ of the roads are illuminated and others are not available for use. It so happens that these roads form a tree, i.e., they are exactly enough to connect any building to another.

The first figure in the image shows the roads at nighttime, while the second one depicts them during the daytime. The third figure is a simpler example that will be used in explanations below.

Each building can be bought and made to be an office. Each month, you will tour the offices, starting from one building, visiting all the other converted office buildings, and finally returning to the initial building. You will use the available roads for this purpose and minimize the total length of the tour, although you aren't certain about the specific time of day.

In the example on the right, in case of opening the offices in the buildings $A$, $D$ and $F$ the tour length would be $6$ during the day and $10$ during the night.

To avoid planning complications, the decision was made to select office buildings in a manner that ensures the minimum length for the tour remains the same both during the day and at night.

Input Format

The first line contains three integers: $N$, $M$ and $T$. $T$ indicates the exact number of offices you plan to open, except when $T = 1$, in which case you can open any number of offices, but at least two.

Each of the following $N$ lines consists of $M$ characters (without spaces). The $j$-th character on the $i + 1$-th line is either 0, 1, 2 or 3, describing roads illuminated during the nighttime from the building on the $i$-th street from the top and $j$-th street from the left:

• 0 indicates no roads leading from this building to its upper or left directions.
• 1 indicates a road from this building to the one directly above it.
• 2 indicates a road from this building to the one directly to its left.
• 3 indicates roads from this building to the buildings directly above it and to its left.

There are exactly $N \times M - 1$ roads and they form a tree.

Output Format

Print one integer: the number of ways modulo $10^9 + 7$.

2 3 2
022
031

12

Corresponds to the image above.

The offices can be opened in the following pairs of buildings: {A, B}, {A, C}, {A, E}, {A, F}, {B, C}, {B, D}, {B, E}, {B, F}, {C, D}, {C, E}, {C, F}, {D, E}.

2 3 3
022
031

10

Same city with $T = 3$. The offices can be opened in the following triplets of buildings: {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}.

2 3 1
022
031

25

In addition to the possibilities for $T = 2$ and $T = 3$ shown above, offices can also be opened in the following ways: {A, B, C, E}, {A, B, C, F}, {B, C, D, E}.

Constraints

• $1 \leq T \leq 3$
• $1 \leq N , M \leq 1\,000$

Subtasks

1. (4 points) $M , N \leq 2$
2. (5 points) $N = 1$
3. (9 points) $T = 2$; $N , M \leq 50$
4. (11 points) $T = 2$
5. (9 points) $T = 3$; $N , M \leq 20$
6. (13 points) $T = 3$
7. (14 points) $T = 1$; $M , N \leq 4$
8. (10 points) $T = 1$; $N , M \leq 50$
9. (9 points) $T = 1$; Road descriptions do not contain character 3.
10. (16 points) $T = 1$