問題文

今、AliceAlice11から99までの自然数を、それぞれのiiについてdid_i個だけ所持しているものとする。(1i9) (1 \le i \le 9)

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

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


S=[1,5,9,1,5], [1,5,5,1,9], [1,1,5,5,9] ,etc.S = [1,5,9,1,5],\ [1,5,5,1,9],\ [1,1,5,5,9] \ ,etc.


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

例えば、S=[1,5,9,1,5]S = [1,5,9,1,5]の時

[1,591,5][1,5 | 9 | 1, 5]と分割すれば、TTの値は 15915=202515 * 9 * 15 = 2025となる。

[1,5,9,15][1,5, 9, 1| 5]と分割すれば、TTの値は 15915=79551591 * 5 = 7955となる。

[1,5,9,1,5][1,5, 9, 1, 5]と分割すれば、TTの値は 15915=1591515915 = 15915となる。

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

最終的に得られるTTの期待値をmod 109+7mod\ 10^9 + 7で求めよ。

入力

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

d1 d2 d3 d4 d5 d6 d7 d8 d9

出力

TTの期待値をmod 109+7mod\ 10^9 + 7で求めよ。

この条件のもとでは T=PQ(Q0 mod 109+7)T = \frac{P}{Q} ( Q \neq 0\ mod\ 10^9 + 7)なる自然数の組(P,Q)(P, Q)が存在することが証明できる。

この時T=PQ1(mod 109+7)T = PQ^{-1}(mod\ 10^9 + 7)を出力せよ。

制約

1i=19di201\le \displaystyle \sum_{i = 1}^{9} d_i \le 20

0di (1i9)0 \le d_i \ (1\le i \le 9)

サンプル

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

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

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1][1,2,3], \ [1, 3, 2], \ [2, 1, 3], \ [2,3,1], \ [3,1,2], \ [3,2,1]

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

S=[1,2,3][123],[12,3],[1,23],[1,2,3]T=123+123+123+1234=47S = [1,2,3] \rightarrow [123], [12,3], [1, 23], [1,2,3] \rightarrow T = \frac{123 + 12*3 + 1 * 23 + 1 * 2 * 3} {4} = 47

S=[1,3,2][132],[13,2],[1,32],[1,3,2]T=132+132+132+1234=49S = [1,3,2] \rightarrow [132], [13,2], [1, 32], [1,3,2] \rightarrow T = \frac{132 + 13*2 + 1 * 32 + 1 * 2 * 3} {4} = 49

S=[2,3,1]T=1612S = [2,3,1] \rightarrow T= \frac{161}{2}

S=[2,1,3]T=77S = [2,1,3] \rightarrow T= 77

S=[3,1,2]T=104S = [3,1,2] \rightarrow T= 104

S=[3,2,1]T=2112S = [3,2,1] \rightarrow T= \frac{211}{2}

 \ SSのパターンはいずれも確率16\frac{1}{6}で発生するため、TTの期待値は47+49+1612+77+104+21126=4636\frac{47 + 49 + \frac{161}{2} + 77 + 104 + \frac{211}{2}}{6} = \frac{463}{6}となる。

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

SSは確率11[1,1,1,1,1][1,1,1,1,1]となる。  \

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

 \

提出


Go (1.21)