← 返回题目列表

AtCoder · iroha2019_day1_k

K. 轮盘赌

中文机器翻译题面 查看原题

配点 : \(600\) 点

这个问题的解释是单击此处。

問題文

Iroha 有 \(N\) 个轮盘和足够的轮盘球。每个磁盘都分配有一个从\(1\)到\(N\)的整数。

整数被写入磁盘周围。具体来说,\(M_i\) 个整数 \(A_{i,1},\A_{i,2},\ \dots\ A_{i,M_i}\) 被写入磁盘 \(i\) 周围。这些整数之间可能存在重复。

另外,如果旋转圆盘 \(i\) 并将球滚动到那里,球将落在写入 \(A_{i,1},\ A_{i,2},\ \dots\ A_{i,M_i}\) 之一的位置。在这种情况下,球体落入\(A_{i, j}\ (1≤j≤M_i)\)的概率为\(1/{M_i}\)。

有一天,伊吕波酱有一个天才的想法,用这些光盘想出了一款游戏。是这样的:

  • 首先,旋转所有圆盘并在每个圆盘上滚动一个球。
  • 按照盘的顺序\(1, 2, \dots N\),连接并读取小球进入处写入的整数。
    • 例如,如果有\(3\)个磁盘,并且在磁盘\(1,2,3\)上写入球所在位置的整数为\(11,2,717\),则将读出\(112717\)。

Iroha-chan 想知道将被大声朗读的整数的期望值。然而,由于她不是程序员,她无法确定期望值。

我不知道你是不是一个优秀的程序员,但请找出对于不是程序员的伊吕波的期望值。

然而,期望值(以下简称\(E\))可能是小数,因此请用\(E \times M_1 \times M_2 \times\ \dots\times\ M_N\)(该值始终是整数)除以\(10^9+7\)求余数。

制約

  • 所有输入均为整数。
  • \(1≤N≤200,000\)
  • \(1≤M_i\(1≤i≤N)\)
  • \(M_1 + M_2 +\ \点\ + M_N≤200,000\)
  • \(1≤A_{i,j}≤10^9\(1≤i≤N,1≤j≤M_i)\)

入力

输入按以下格式给出:

\(N\)
\(M_1\ A_{1, 1}\ A_{1, 2}\ \dots\ A_{1, M_1}\)
\(M_2\ A_{2, 1}\ A_{2, 2}\ \dots\ A_{2, M_2}\)
\(\vdots\)
\(M_N\ A_{N, 1}\ A_{N, 2}\ \dots\ A_{N, M_N}\)

出力

打印 \(E \times M_1 \times M_2 \times\ \dots\times\ M_N\) 除以 \(10^9+7\) 的余数。


入力例 1

2
2 11 3
2 9 14

出力例 1

1586

在此输入示例中,有 \(2\) 个磁盘,分别标记为 \(11, 3\) 和 \(9, 14\)。

有 \(4\) 个可能的整数可以读出:\(119, 1114, 39, 314\),每个整数的概率相等,因此期望值为 \(\frac{119+1114+39+314}{4}=396.5\)。

答案是 \(396.5 \times 2 \times 2 = 1586\)。


入力例 2

3
3 172 11 31
2 701 5
2 12 21

出力例 2

43651798

可能读出的整数为:17270121\)。


入力例 3

3
1 1000000000
1 1000000000
1 1000000000

出力例 3

999966190

此输入示例始终为 \(100000000010000000001000000000\)。

请注意,我们正在寻找除以 \(10^9+7\) 时的余数。


入力例 4

10
5 371094 2597554 69382646 8 99062422 
12 6553139 40789 2519037 81594 46824888 84 4912 27575435 2774 4060 331605 7438162 
5 36 65156096 71969458 2 221919 
7 738734 979629710 4841 7027881 6107446 267092962 634173170 
9 16252 6294622 6670 932636725 8 221842 111612 86053044 823517544 
3 589 70 347090831 
9 7853 6 3174 1 14675 42 10793760 777031 23350 
15 5143 23971 93 68615 4384503 3 5867 96099 81021 10506439 137503 43398308 52626 9895727 3 
6 9819 93 808 2025523 36 593697 
3 497384 767669 80690

出力例 4

993753975