장터판 (Large)

지리산을 오르다가 장이 선 장터에 들렀다. 사람이 몰린 한쪽에서 누군가 게임을 열고 있다.

이 게임은 탁자 위에 놓인 $N$행 $M$열 격자판으로 진행한다. 격자의 각 칸에는 $K$면체 주사위가 하나씩 놓여 있다.

주최자는 주사위 중 일부를 특정 면이 보이도록 고정하고, 나머지는 자유롭게 움직이도록 둔다. 그다음 판을 흔들면 고정되지 않은 주사위, 즉 자유로운 주사위는 $K$개의 면 중 하나가 보이는 채로 멈춘다. 각 면이 보일 확률은 모두 $1/K$로 같고, 주사위마다 서로 독립이다.

판이 멈추면 칸마다 점수를 매긴다. 방향은 가로, 세로, 두 대각선의 네 가지이고, 각 칸의 점수는 다음과 같이 정한다.

1. 그 칸을 포함해 한 방향으로 연속한 네 칸이 모두 같은 면을 보이는 경우가 있으면 $S_4$점.
2. 1번에 해당하지 않고, 그 칸을 포함해 한 방향으로 연속한 세 칸이 모두 같은 면을 보이는 경우가 있으면 $S_3$점.
3. 2번에 해당하지 않고, 그 칸을 포함해 한 방향으로 연속한 두 칸이 모두 같은 면을 보이는 경우가 있으면 $S_2$점.
4. 어느 경우에도 해당하지 않으면 0점.

모든 칸의 점수를 더한 값이 그 게임의 점수다.

주사위를 고정하는 작업이 끝났고, 이제 판을 흔들 차례다. 판을 흔들었을 때 얻는 점수의 기댓값을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 여섯 개 $N$, $M$, $K$, $S_4$, $S_3$, $S_2$가 공백으로 구분되어 주어진다. $N$은 판의 행 수, $M$은 열 수, $K$는 주사위 면의 수이고, $S_4$, $S_3$, $S_2$는 문제에서 설명한 점수다.

이어지는 $N$개의 줄은 판의 맨 위 행부터 차례대로 각 행의 상태를 나타낸다. 각 줄은 길이가 $M$인 문자열이고, 왼쪽부터 그 행에 놓인 주사위의 상태를 나타낸다. 고정된 주사위는 보이는 면의 번호인 1 이상 $K$ 이하의 숫자 한 자리로, 자유로운 주사위는 물음표 ?로 주어진다.

제한

• $1 \le T \le 50$
• $2 \le N \le 100$, $2 \le M \le 100$
• $2 \le K \le 9$
• $0 \le S_2 \le S_3 \le S_4 \le 100$
• 자유로운 주사위의 수에는 제한이 없다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 케이스의 점수 기댓값이다. $y$는 소수점 아래 일곱째 자리까지 반올림해 소수점 아래 일곱 자리로 출력한다.