헥사코인 잼

Code Jam 팀이 처음 만든 암호화폐 jamcoin은 널리 쓰이지 못했습니다. 올해는 16진법을 쓴다는 점에서 이름 붙인 hexacoin으로 다시 도전합니다. $D$자리 hexacoin을 채굴하려면 선행 0을 포함해 정확히 $D$자리 16진수로 이루어진 정수를 다뤄야 합니다. 각 값은 $0$ 이상 $16^D - 1$ 이하의 정수를 나타냅니다. 16진수 자리는 여느 때처럼 0부터 9까지의 숫자와 대문자 A부터 F까지로 나타냅니다. 예를 들어 $D=3$일 때 F2B, 0C8, 000은 유효한 값이며, 각각 10진수 3883, 200, 0에 대응합니다. 반면 1234, DF, C0DE, JAM은 $D=3$일 때 유효한 값이 아닙니다.

$D$자리 16진수 값끼리 더할 때 넘치는 자리 올림은 버립니다. 즉 덧셈은 $16^D$를 법으로 한 나머지로 계산합니다. 예를 들어 F2B + 0C8 = FF3(10진수 4083)이고, F2B + F2B = E56입니다. 합은 7766이고, $16^3$을 법으로 한 나머지가 3670이므로 E56은 10진수 3670입니다.

$D$자리 hexacoin을 채굴하려면 컴퓨터가 다음 단계를 수행해야 합니다.

1. $N$개의 $D$자리 16진수 값으로 이루어진 목록 $L$을 고릅니다. 원소는 $L_1, L_2, \ldots, L_N$입니다.
2. $D$자리 16진수 값의 목표 범위를 고릅니다. $S$부터 $E$까지의 수(양 끝 포함)입니다.
3. 16진수 자리 0부터 F까지의 순열 $P$를 가능한 $16!$가지 순열 중에서 균등한 확률로 무작위로 고릅니다.
4. $P$를 목록에 있는 모든 수의 모든 자리에 적용해, $N$개의 $D$자리 16진수 값으로 이루어진 새 목록 $L'$을 만듭니다. 정확히 말하면 $L'$의 $i$번째 원소의 $j$번째 자리는 $L$의 $i$번째 원소의 $j$번째 자리에 $P$를 적용한 결과입니다.
5. $L'$에서 원소 두 개를 비복원으로 고릅니다. 가능한 모든 선택지 중에서 균등한 확률로 고르며, 순열을 고른 것과는 독립적으로 고릅니다.
6. 고른 두 원소의 합(넘치는 자리 올림은 버림)을 계산합니다.

마지막 단계에서 계산한 합이 $S$ 이상 $E$ 이하이면 hexacoin을 찾은 것입니다. 예를 들어 다음과 같다고 합시다.

• $L$ = [134, 000, FFB, 000, AA9]
• $S$ = 85C, $E$ = EDF
• 컴퓨터가 우연히 $P$ = (0 → 4, 1 → A, 2 → 2, 3 → 8, 4 → 9, 5 → B, 6 → C, 7 → 7, 8 → F, 9 → 1, A → 0, B → 3, C → 5, D → 6, E → E, F → D)를 고른다.

그러면 $P$를 $L$에 적용한 결과 $L'$은 [A89, 444, DD3, 444, 001]입니다. $P$는 $S$와 $E$에는 적용하지 않는다는 점에 주의하세요.

고를 수 있는 값의 쌍은 $(5 \times 4) / 2 = 10$개이며, 각 쌍이 선택될 확률은 $1/10$입니다. 범위 안에 드는 합은 A89 + DD3 = 85C, 444 + 444 = 888, A89 + 001 = A8A, DD3 + 001 = DD4, A89 + 444 = ECD(두 번)뿐입니다.

첫 두 단계는 이미 끝났고, 골라진 목록 $L$과 범위 [$S$, $E$]를 알고 있습니다. 나머지 과정을 마쳤을 때 hexacoin을 찾을 확률은 얼마입니까?

입력의 첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 나옵니다. 각 테스트 케이스는 세 줄로 이루어집니다. 첫 줄에는 정수 $N$과 $D$가 있으며, 주어진 목록의 크기와 다룰 자리 수를 뜻합니다. 둘째 줄에는 두 개의 $D$자리 16진수 $S$와 $E$가 있으며, 각각 목표 범위의 하한과 상한(양 끝 포함)입니다. 셋째 줄에는 목록의 값을 나타내는 $D$자리 16진수 $N$개 $L_1, L_2, \ldots, L_N$이 있습니다.

각 테스트 케이스마다 Case #x: y z 형식의 한 줄을 출력합니다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$와 $z$는 음이 아닌 정수입니다. 분수 $y/z$는 위의 조건에서 hexacoin을 찾을 확률을 나타냅니다. $x$, $y$, $z$는 모두 10진수로 씁니다. $y$와 $z$의 가능한 값이 여러 개이면 $z$가 최소가 되는 값을 고릅니다.

• $2 \le N \le 450$.
• $S$는 정확히 $D$개의 문자로 이루어집니다.
• $S$의 각 문자는 16진수 자리입니다.
• $E$는 정확히 $D$개의 문자로 이루어집니다.
• $E$의 각 문자는 16진수 자리입니다.
• $S \le E$.
• 모든 $i$에 대해 $L_i$는 정확히 $D$개의 문자로 이루어집니다.
• 모든 $i$에 대해 $L_i$의 각 문자는 16진수 자리입니다.

샘플 케이스 #1에서 목표 범위는 값 10 하나뿐입니다. 결과의 끝자리가 0이므로, 마지막 자리 0과 F에 배정된 값의 합도 끝자리가 0이어야 합니다. $P[0]$과 $P[F]$는 서로 다른 값이므로 합이 정확히 0일 수는 없습니다. 따라서 $P[0] + P[F]$는 (16진수로) 10이어야 합니다. 이를 만족하는 서로 다른 숫자 쌍은 7개입니다. $P[0]$과 $P[F]$가 둘 다 8일 수는 없습니다. 7개 쌍 모두 올림이 버려진 뒤 전체 합이 10이 됩니다. 따라서 0과 F에 서로 다른 숫자를 배정하는 방법 중 hexacoin으로 이어지는 것은 14개입니다. 이 두 자리에 배정할 수 있는 방법은 $16 \times 15$가지이므로 결과는 $14/240 = 7/120$입니다.

샘플 케이스 #2에서는 결과가 정확히 11일 확률을 샘플 케이스 #1의 결과에 더해야 합니다. 이것이 일어나는 경우는 0과 F가 각각 0과 1에 배정될 때뿐이며, 순서는 어느 쪽이든 상관없습니다. 그 확률은 $2/240=1/120$이므로, 전체 합은 $7/120 + 1/120 = 8/120 = 1/15$입니다.

샘플 케이스 #3에서는 컴퓨터가 어떤 순열과 어떤 수 쌍을 고르든, 같은 끝자리로 끝나는 두 수를 더하게 된다는 점에 주목하세요. 그러면 $16^3$을 법으로 한 나머지를 구한 뒤에도 결과가 짝수입니다. 범위 안의 유일한 값은 홀수이므로 이 경우에는 hexacoin을 채굴할 가망이 없습니다. 0 2는 $z$가 최소가 아니므로 답의 올바른 표현이 아닙니다.