꿀 투어

작은 곰 코마는 꿀을 아주 좋아한다. 어느 날 코마는 꿀로 가득 찬 창고를 발견했다. 이 창고에는 입구가 $M$개, 출구가 $M$개 있고, 미로처럼 매우 복잡하게 생겼다. 코마는 곧 창고의 구조를 파악하고 지도를 그렸다. 지도는 $N \cdot K$행 $M$열의 2차원 격자이다. 각 칸에는 장애물 또는 꿀통이 있다. 지도에는 특별한 성질이 하나 있다. 같은 $N \times M$ 격자가 $K$개 위아래로 똑같이 이어 붙어 있다는 것이다.

$M$개 열 각각의 윗변은 입구, 아랫변은 출구이다. 코마는 다음 규칙에 따라 창고를 둘러본다.

1. 코마는 입구 중 하나로 들어가 출구 중 하나로 나간다.
2. 코마는 변을 공유하는 칸으로 이동할 수 있다.
3. 코마는 장애물이 없는 칸에만 머무를 수 있다.
4. 코마는 각 칸을 최대 한 번 방문할 수 있다.
5. 코마는 방문한 꿀통에서 꿀을 먹을 수 있다.

코마는 가능한 한 많은 꿀통을 방문하려 한다. 각 입구 $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$ 행렬 두 개를 차례로 출력하라. 첫 번째 행렬에는 방문할 수 있는 꿀통의 최대 개수를, 두 번째 행렬에는 그 최대 개수에 도달하는 방법의 수를 $10^{9} + 7$로 나눈 나머지를 쓴다. 각 행렬의 $i$번째 줄 $j$번째 수는 $i$번 입구로 들어가 $j$번 출구로 나가는 경우에 해당한다.