Opening Offices

Time limit1sMemory limit1024 MB

Summary

Count the ways to choose T office buildings on a grid so that the shortest closed tour is the same on the full grid and on the night spanning tree, modulo 1000000007.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

A company is opening offices in a city with $N$ horizontal streets and $M$ vertical streets, with a building at each intersection. Each building is connected to its neighbors by up to two vertical and two horizontal roads, and every road has length 1.

At night, only $N \times M - 1$ of the roads are illuminated, and the rest cannot be used. The illuminated roads form a tree, so any building can reach any other building.

The first figure shows the roads at night, and the second shows the roads during the day. The third figure is a smaller example used in the explanations below.

After choosing the office buildings, you tour the offices every month. You start at one building, visit all the other chosen offices, and return to the starting building. You use only the available roads and minimize the total length of the tour. You do not know whether the tour happens during the day or at night.

In the example on the right, if offices open at buildings A, D, and F, the tour length is 6 during the day and 10 at night.

To keep planning simple, choose the office buildings so that the minimum tour length is the same during the day and at night. Count the ways to choose office buildings that satisfy this. Two choices differ if at least one building is in one choice and not the other. The count can be large, so output it modulo $10^9 + 7$ . The allowed number of offices is in the input format.

Input

The first line contains three integers $N$ , $M$ , and $T$ . $T$ is the exact number of offices to open. However, if $T = 1$ , you may open any number of offices, but at least two.

Each of the next $N$ lines contains $M$ characters with no spaces. The $j$ -th character on the $(i+1)$ -th line describes the night roads from the building in row $i$ (from the top) and column $j$ (from the left):

0: no road leads from this building up or left.
1: a road leads from this building to the building directly above it.
2: a road leads from this building to the building directly to its left.
3: roads lead from this building to the building directly above it and to the building directly to its left.

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

Output

Print the number of ways modulo $10^9 + 7$ on one line.

Constraints

$1 \le T \le 3$
$1 \le N, M \le 1\,000$

Examples3

Example 1
Input
```
2 3 2
022
031
```
Expected output
```
12
```
Example 2
Input
```
2 3 3
022
031
```
Expected output
```
10
```
Example 3
Input
```
2 3 1
022
031
```
Expected output
```
25
```