Easy Random Product

2 secs 1024 MB
hide's icon hide

問題文

AliceAlice11以上99以下の自然数のみから構成される長さNNの自然数配列SSを所持している。

その後、得られた配列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で求めよ。

入力

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

n
S_1S_2...S_n

出力

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)を出力せよ。

制約

1n1001\le n \le 100

1Si9(1in)1 \le S_i \le 9(1\le i \le n)

サンプル

入力1
3
123
出力1
47

この時、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

入力2
5
11111
出力2
250001034

 \

入力3
15
314159265358979
出力3
26596503

 \

Submit


Go (1.21)