問題文
今、Aliceは1から9までの自然数を、それぞれのiについてdi個だけ所持しているものとする。(1≤i≤9)
Aliceはこれら全ての数字をランダムな順番で取り出し、その順に要素を配列に保存した結果配列Sを得た。
例えば、始めに所持していた数字が(1,1,5,5,9)であった場合、Sとして以下のようなものが考えられる。
S=[1,5,9,1,5], [1,5,5,1,9], [1,1,5,5,9] ,etc.
その後、得られた配列Sをいくつかの空でない連続部分列に分け、各部分列を1つの数字とみなした後にそれらの総積をTとした。
例えば、S=[1,5,9,1,5]の時
[1,5∣9∣1,5]と分割すれば、Tの値は 15∗9∗15=2025となる。
[1,5,9,1∣5]と分割すれば、Tの値は 1591∗5=7955となる。
[1,5,9,1,5]と分割すれば、Tの値は 15915=15915となる。
なお、複数の分割が考えられる場合、Aliceはそのうちいずれかをランダムに選択するものとする。
最終的に得られるTの期待値をmod 109+7で求めよ。
入力
入力は以下の形式で与えられる。
d1 d2 d3 d4 d5 d6 d7 d8 d9
出力
Tの期待値をmod 109+7で求めよ。
この条件のもとでは T=QP(Q=0 mod 109+7)なる自然数の組(P,Q)が存在することが証明できる。
この時T=PQ−1(mod 109+7)を出力せよ。
制約
・1≤i=1∑9di≤20
・0≤di (1≤i≤9)
サンプル
考えられるSは以下の6パターン考えられる。
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]
この時、それぞれのSに対するTの期待値は以下のようになる。
S=[1,2,3]→[123],[12,3],[1,23],[1,2,3]→T=4123+12∗3+1∗23+1∗2∗3=47
S=[1,3,2]→[132],[13,2],[1,32],[1,3,2]→T=4132+13∗2+1∗32+1∗2∗3=49
S=[2,3,1]→T=2161
S=[2,1,3]→T=77
S=[3,1,2]→T=104
S=[3,2,1]→T=2211
Sのパターンはいずれも確率61で発生するため、Tの期待値は647+49+2161+77+104+2211=6463となる。
Sは確率1で[1,1,1,1,1]となる。