Easy Random Product

2 secs 1024 MB
hide

問題文


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

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

例えば、の時

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

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

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

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

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

入力


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

n
S_1S_2...S_n

出力


の期待値をで求めよ。

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

この時を出力せよ。

制約


サンプル


入力1
3
123
出力1
47

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

入力2
5
11111
出力2
250001034

入力3
15
314159265358979
出力3
26596503

Submit


Go (1.14)