#ZF1078. 煎饼的 MEX

煎饼的 MEX

Description

定义一个数字序列的 MEX,为其中最小没有出现过的非负整数。

现在有一个长为 nn 的整数序列 {ai}\{a_i\},jbgg 可以在其中自由选择三个数(三个数在序列中的下标不能相同),并获得这三个数的 MEX。jbgg 想知道他获得 MEX 的期望是多少。

答案可能很大,请对 998244353998244353 取模。

Format

Input

第一行有一个正整数 nn,其中 3n1053 \leqslant n \leqslant 10^5

接下来一行有 nn 个整数 a1,,ana_1, \cdots, a_n,其中 0ai1050 \leqslant a_i \leqslant 10^5

Output

一个数字,表示期望,对 998244353998244353 取模。

有理数取模:如果答案是 PQ\frac{P}{Q} 的形式,若存在 RR 满足 QR1(mod998244353)QR \equiv 1 \pmod {998244353},那么取模后的答案是 PRmod998244353PR \bmod 998244353

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

对于第一个样例:

所有可能选取的下标集合为 {1,2,3},{1,2,4},{1,3,4},{2,3,4}\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\}。 它们对应的 MEX 值分别为:3,2,1,03,2,1,0,则期望为 32\frac{3}{2}

Limitation

1s, 1024KiB for each test case.