장터판 (Small)

문제

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

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

주최자는 주사위 중 일부를 특정 면이 보이도록 고정하고, 나머지는 자유롭게 구르도록 둔다. 그런 다음 판을 흔들면 고정하지 않은 주사위(자유로운 주사위)가 구르다가 $K$ 개의 면 중 하나를 보인다. 어느 면이 보일 확률은 $K$ 개 면이 모두 같고, 주사위마다 독립이다.

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

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

어느 항목에도 해당하지 않는 칸은 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 8$ , $2 \le M \le 8$
$2 \le K \le 9$
$0 \le S_2 \le S_3 \le S_4 \le 100$
한 판에 있는 자유로운 주사위는 0개 이상 4개 이하다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 그 케이스의 점수 기댓값이다.

$y$ 는 소수점 아래 일곱째 자리까지 적는다. 여덟째 자리 아래는 가장 가까운 값으로 반올림하고, 정확히 중간인 값은 0에서 먼 쪽으로 올린다. 예를 들어 기댓값이 정확히 $38.42578125$ 이면 38.4257813을 출력한다. 기댓값이 정수여도 1600.0000000처럼 소수점 아래 일곱 자리를 모두 적는다.