P13448 [GCJ 2009 Finals] Year of More Code Jam

新的一年带来了新的日历、新的挑战，以及生活中更多的乐趣。然而，有些事情永远不会改变。精彩的编程比赛依旧层出不穷，而我们的主角 Sphinny 对这些比赛的热情始终如一。 Sphinny 对若干项锦标赛感兴趣。每项锦标赛都包含若干轮。每项锦标赛的主办方尚未确定比赛的开始日期，但已经决定了该锦标赛将包含多少轮，以及每一轮距离比赛开始日的天数。 在某些情况下，不同锦标赛的若干轮可能会安排在同一天举行。由于 Sphinny 非常热爱解题，如果同一天有更多的轮次举行，她会更加开心。她的幸福值计算方式如下：对于每一天，若当天有 $S$ 轮比赛，则她的幸福值增加 $S^2$。她的初始幸福值为 $0$（别担心——$0$ 也是个很幸福的起点）。 下图展示了三项锦标赛，每种颜色代表一项锦标赛，Sphinny 的总幸福值为 $20$。有一项锦标赛在当年的第 $2$ 天开始，一项在第 $5$ 天开始，一项在第 $6$ 天开始。  一年共有 $N$ 天。每项锦标赛都可以等概率地在这 $N$ 天中的任意一天开始。今年的大问题是：Sphinny 的期望幸福值是多少？ 作为一个完美主义者，她不会只求近似解，而是想要精确的答案。锦标赛的数量为 $T$，因此一共有 $N^T$ 种等可能的锦标赛开始日期的组合。她希望将期望幸福值写成 $K+A/B$ 的形式，其中 $K$ 和 $B$ 为正整数，$A$ 为非负整数且 $A < B$。如果 $A$ 为零，则 $B$ 必须为 $1$；否则 $A$ 和 $B$ 不能有大于 $1$ 的公因数。 如果某项锦标赛开始得太晚，导致其某些轮次安排在下一年，则这些轮次不会对 Sphinny 当年的幸福值产生任何贡献。

输入的第一行为一个整数 $C$，表示测试用例数量。接下来有 $C$ 组测试数据。每组测试数据的第一行为 $N\ T$ 其中 $N$ 表示一年中的天数，$T$ 表示锦标赛数量。接下来有 $T$ 行，每行描述一项锦标赛，格式如下： $m\ d_2\ d_3\ \ldots\ d_m$ 表示该锦标赛共有 $m$ 轮，第 $i$ 轮将在该锦标赛开始后的第 $d_i$ 天举行。每项锦标赛的第一轮总是在第 $1$ 天举行（即 $d_1=1$）。

对于每组测试数据，输出一行，格式如下： Case #$X$: $K+A/B$ 其中 $X$ 为测试编号（从 $1$ 开始），$K$、$A$、$B$ 的含义如上所述。

**限制条件** - $1 \leq C \leq 50$ - $1 \leq N \leq 10^{9}$ - $2 \leq m \leq 50$ - $1 < d_2 < d_3 < \ldots < d_m \leq 10000$ **小数据集（5 分）** - $1 \leq T \leq 2$ **大数据集（12 分）** - $1 \leq T \leq 50$ 翻译由 ChatGPT-4.1 完成。