小熊 Koma 非常喜欢蜂蜜。有一天，Koma 发现了一个装满蜂蜜的仓库。这个仓库有 $M$ 个入口和 $M$ 个出口，结构非常复杂，就像一个迷宫。很快，Koma 弄清了仓库的结构并绘制了一张地图。这张地图是一个 $N \cdot K$ 行 $M$ 列的二维网格。网格中的每个方格要么包含障碍物，要么包含一个蜂蜜罐。地图的一个奇妙特性是，它实际上由 $K$ 个相同的 $N \times M$ 网格垂直堆叠而成！

网格每一列的顶端是一个入口，每一列的底端是一个出口。Koma 决定在仓库中进行一次游览，并遵守以下规则：

1. Koma 从其中一个入口进入仓库，并从其中一个出口离开。
2. Koma 可以在共享边的方格之间移动。
3. 在任何时刻，Koma 只能占据不包含障碍物的方格。
4. Koma 每个方格最多只能访问一次。
5. Koma 可以吃掉他访问的每个方格中的蜂蜜。

Koma 希望尽可能多地访问蜂蜜罐。对于每一个可能的入口 $i$ 和每一个可能的出口 $j$，计算两个整数：当他从第 $i$ 个入口进入并从第 $j$ 个出口离开时，他能访问的蜂蜜罐的最大数量，以及实现该最大数量的最优路径数量。由于路径数量可能非常大，请将其对 $10^9 + 7$ 取模。

输入格式

第一行包含三个整数 $N, M$ 和 $K$ ($1 \le N \le 5, 2 \le M \le 7, 2 \le N \cdot M \le 25, 1 \le K \le 10^9$)。

接下来有 $N$ 行，每行包含 $M$ 个字符。它们描述了网格的重复模式。字符 ‘.’ 表示包含蜂蜜罐的方格，字符 ‘X’ 表示包含障碍物的方格。

输出格式

依次打印两个 $M \times M$ 的矩阵。第一个矩阵包含 Koma 可以访问的蜂蜜罐的最大数量。第二个矩阵包含访问最大数量蜂蜜罐的可能路径数量，对 $10^9 + 7$ 取模。在每个矩阵中，第 $i$ 行的第 $j$ 个数字对应于 Koma 从第 $i$ 个入口进入并从第 $j$ 个出口离开的情况。

样例

样例输入 1

2 2 3
..
.X

样例输出 1

6 0
7 0
1 0
1 0