問題文
Aliceは1以上9以下の自然数のみから構成される長さNの自然数配列Sを所持している。
その後、得られた配列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で求めよ。
入力
入力は以下の形式で与えられる。
出力
Tの期待値をmod 109+7で求めよ。
この条件のもとでは T=QP(Q=0 mod 109+7)なる自然数の組(P,Q)が存在することが証明できる。
この時T=PQ−1(mod 109+7)を出力せよ。
制約
・1≤n≤100
・1≤Si≤9(1≤i≤n)
サンプル
この時、Sに対するTの期待値は以下のようになる。
S=[1,2,3]→[123],[12,3],[1,23],[1,2,3]→T=4123+12∗3+1∗23+1∗2∗3=47