19513번 - Honey Tour 다국어

A little bear Koma likes honey very much. One day, Koma found a storehouse full of honey. The storehouse had $M$ entrances and $M$ exits, and it turned out to be very complicated, like a maze. Soon Koma understood the structure of the storehouse and drew a map of it. The map is a two-dimensional grid of $N \cdot K$ rows and $M$ columns. Each square of the grid contains either an obstacle or a honey pot. An amazing property of the map is that it actually consists of $K$ identical copies of the same $N \times M$ grid, placed one below the other!

The top side of each of the $M$ columns of the grid is an entrance, and the bottom side of each column is an exit. Koma decides to take a tour in the storehouse obeying the following rules:

1. Koma enters the storehouse through one of the entrances, and leaves through one of the exits
2. Koma can move from one square to another if these squares share a side.
3. At any point of time, Koma can occupy a square only if this square contains no obstacle.
4. Koma can visit each square at most once.
5. Koma can eat from each honey pot he visits.

Koma wants to visit as much honey pots as possible. For each possible entrance $i$ and each possible exit $j$, compute two integers: the maximum number of honey pots he can visit when he enters through $i$-th entrance and leaves through $j$-th exit and the number of such optimal tours. As the number of tours can be rather large, find it modulo $10^{9} + 7$.

The first line of input contains three integers $N$, $M$ and $K$ ($1 \le N \le 5$, $2 \le M \le 7$, $2 \le N \cdot M \le 25$, $1 \le K \le 10^9$).

After that, there are $N$ lines each of which contains $M$ characters. They describe the repeating pattern of the grid. A character '.' means a square containing a honey pot, and a character 'X' means a square containing an obstacle.

Print two $M \times M$ matrices, one after another. The first matrix must contain the maximum number of honey pots Koma can visit. The second matrix must contain the number of possible ways to visit the maximum number of honey pots, taken modulo $10^{9} + 7$. In each of the matrices, $j$-th number on $i$-th line corresponds to the case where Koma enters through $i$-th entrance and leaves through $j$-th exit.