#ZF1078. 煎饼的 MEX
煎饼的 MEX
Description
定义一个数字序列的 MEX,为其中最小没有出现过的非负整数。
现在有一个长为 的整数序列 ,jbgg 可以在其中自由选择三个数(三个数在序列中的下标不能相同),并获得这三个数的 MEX。jbgg 想知道他获得 MEX 的期望是多少。
答案可能很大,请对 取模。
Format
Input
第一行有一个正整数 ,其中 。
接下来一行有 个整数 ,其中 。
Output
一个数字,表示期望,对 取模。
有理数取模:如果答案是 的形式,若存在 满足 ,那么取模后的答案是 。
Samples
4
0 1 2 3
499122178
5
0 0 1 2 3
798595484
10
0 1 2 3 4 5 6 7 8 9
623902721
Note
对于第一个样例:
所有可能选取的下标集合为 。 它们对应的 MEX 值分别为:,则期望为 。
Limitation
1s, 1024KiB for each test case.