대회가 더 많은 해

새해가 오면 달력이 바뀌고 새로운 프로그래밍 대회가 여럿 열린다. 스피니는 올해도 대회 일정에 맞춰 한 해를 계획한다.

스피니가 관심을 두는 대회가 여럿 있다. 대회마다 라운드 수가 정해져 있고, 각 라운드가 그 대회의 시작일로부터 며칠째에 열리는지도 정해져 있다. 다만 주최 측은 대회를 며칠에 시작할지는 아직 정하지 않았다.

서로 다른 대회의 라운드가 같은 날에 겹칠 수 있다. 스피니는 하루에 라운드가 많이 열릴수록 더 즐거워한다. 어떤 날에 라운드가 $S$개 열리면 즐거움이 $S^2$만큼 늘어난다. 즐거움은 0에서 시작한다.

아래 그림은 색이 다른 세 대회를 나타낸다. 한 대회는 그 해의 2일째에, 다른 대회는 5일째에, 나머지 대회는 6일째에 시작하며, 이때 스피니의 즐거움은 모두 합쳐 20이다.

한 해는 $N$일이다. 각 대회는 $N$일 가운데 하루에서 시작하고, 모든 날이 뽑힐 확률은 같으며, 대회끼리는 서로 독립이다. 스피니의 즐거움의 기댓값을 구하라.

스피니는 근삿값을 원하지 않는다. 대회는 $T$개이고 시작일을 정하는 방법은 $N^T$가지이며 각 방법의 확률은 모두 같다. 기댓값을 $K+A/B$ 꼴로 나타내라. $K$와 $B$는 양의 정수이고, $A$는 $B$보다 작은 음이 아닌 정수다. $A$가 0이면 $B$는 1이어야 하고, 그렇지 않으면 $A$와 $B$의 최대공약수는 1이어야 한다.

대회가 늦게 시작하면 일부 라운드가 다음 해로 넘어간다. 다음 해로 넘어간 라운드는 올해의 즐거움에 더해지지 않는다.

첫 줄에 테스트 케이스의 수 $C$가 주어진다. 각 테스트 케이스의 첫 줄은 다음 형식이다.

N T

$N$은 한 해의 날 수, $T$는 대회의 수다. 이어서 대회마다 한 줄씩 모두 $T$개의 줄이 다음 형식으로 주어진다.

m d2 d3 ... dm

이 대회의 라운드는 $m$개이고, $i$번째 라운드는 대회 시작일부터 세어 $d_i$일째에 열린다. 첫 라운드는 언제나 1일째이므로 $d_1 = 1$은 입력에 나오지 않는다.

제한

• $1 \le C \le 50$
• $1 \le N \le 10^9$
• $1 \le T \le 50$
• $2 \le m \le 50$
• $1 < d_2 < d_3 < \dots < d_m \le 10000$

각 테스트 케이스마다 한 줄에 다음 형식으로 출력한다.

Case #X: K+A/B

$X$는 1부터 시작하는 테스트 케이스 번호이고, $K$, $A$, $B$는 문제에서 설명한 값이다.