Random Product

今、はからまでの自然数を、それぞれのについて個だけ所持しているものとする。

はこれら全ての数字をランダムな順番で取り出し、その順に要素を配列に保存した結果配列を得た。

例えば、始めに所持していた数字がであった場合、として以下のようなものが考えられる。

その後、得られた配列をいくつかの空でない連続部分列に分け、各部分列をつの数字とみなした後にそれらの総積をとした。

例えば、の時

と分割すれば、の値は となる。

と分割すれば、の値は となる。

と分割すれば、の値は となる。

なお、複数の分割が考えられる場合、はそのうちいずれかをランダムに選択するものとする。

最終的に得られるの期待値をで求めよ。

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

d1 d2 d3 d4 d5 d6 d7 d8 d9

の期待値をで求めよ。

この条件のもとでは なる自然数の組が存在することが証明できる。

この時を出力せよ。

・

・

1 1 1 0 0 0 0 0 0

166666745

考えられるは以下のパターン考えられる。

この時、それぞれのに対するの期待値は以下のようになる。

のパターンはいずれも確率で発生するため、の期待値はとなる。

5 0 0 0 0 0 0 0 0

250001034

は確率でとなる。

1 2 5 2 1 2 2 1 4

482403035