問題文


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

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

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



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

例えば、の時

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

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

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

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

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

入力


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

d1 d2 d3 d4 d5 d6 d7 d8 d9

出力


の期待値をで求めよ。

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

この時を出力せよ。

制約


サンプル


入力1
1 1 1 0 0 0 0 0 0
出力1
166666745

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

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

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

入力2
5 0 0 0 0 0 0 0 0
出力2
250001034

は確率となる。

入力3
1 2 5 2 1 2 2 1 4
出力3
482403035

Submit


Go (1.14)