配点 : $100$ 点

問題文

$N$ 枚の皿があります。 皿には $1, 2, \ldots, N$ と番号が振られています。 最初、各 $i$ ($1 \leq i \leq N$) について、皿 $i$ には $a_i$ ($1 \leq a_i \leq 3)$ 個の寿司が置かれています。

すべての寿司が無くなるまで、太郎君は次の操作を繰り返し行います。

• $1, 2, \ldots, N$ の目が等確率で出るサイコロを振り、出目を $i$ とする。 皿 $i$ に寿司がある場合、皿 $i$ の寿司を $1$ 個食べる。 皿 $i$ に寿司が無い場合、何も行わない。

すべての寿司が無くなるまでの操作回数の期待値を求めてください。

制約

• 入力はすべて整数である。
• $1 \leq N \leq 300$
• $1 \leq a_i \leq 3$

入力

入力は以下の形式で標準入力から与えられる。

$N$

$a_1$ $a_2$ $\ldots$ $a_N$

出力

すべての寿司が無くなるまでの操作回数の期待値を出力せよ。 相対誤差が $10^{-9}$ 以下ならば正解となる。

3
1 1 1

5.5

$1$ 個目の寿司を食べるまでの操作回数の期待値は $1$ です。 その後、$2$ 個目の寿司を食べるまでの操作回数の期待値は $1.5$ です。 その後、$3$ 個目の寿司を食べるまでの操作回数の期待値は $3$ です。 よって、全体の操作回数の期待値は $1 + 1.5 + 3 = 5.5$ です。

1
3

3

例えば、3.00, 3.000000003, 2.999999997 などを出力しても正解となります。

2
1 2

4.5

10
1 3 2 3 3 2 3 2 1 3

54.48064457488221