Honey Tour

A little bear Koma likes honey very much. One day, Koma found a storehouse full of honey. The storehouse has $M$ entrances and $M$ exits, and its layout is as complicated as a maze. Soon Koma understood the structure and drew a map of it. The map is a two-dimensional grid of $N \cdot K$ rows and $M$ columns. Each square contains either an obstacle or a honey pot. The map has one special property: it consists of $K$ identical copies of the same $N \times M$ grid, stacked one below the other.

The top side of each of the $M$ columns is an entrance, and the bottom side of each column is an exit. Koma takes a tour through the storehouse under these rules:

1. Koma enters through one of the entrances and leaves through one of the exits.
2. Koma can move from one square to another if the two squares share a side.
3. Koma can occupy a square only if the square contains no obstacle.
4. Koma can visit each square at most once.
5. Koma can eat from each honey pot visited.

Koma wants to visit as many honey pots as possible. For each entrance $i$ and each exit $j$, compute two integers: the maximum number of honey pots Koma can visit when entering through the $i$-th entrance and leaving through the $j$-th exit, and the number of tours that reach this maximum. The number of tours can be large, so print it modulo $10^{9} + 7$.

The first line 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}$).

The next $N$ lines each contain $M$ characters that describe the repeating pattern. A '.' marks a square with a honey pot, and an 'X' marks a square with an obstacle.

Print two $M \times M$ matrices, one after another. The first matrix holds the maximum number of honey pots Koma can visit. The second matrix holds the number of tours that reach that maximum, modulo $10^{9} + 7$. The $j$-th number on the $i$-th line corresponds to entering through the $i$-th entrance and leaving through the $j$-th exit.