AT_s8pc_1_e 散歩 (E869120 and Path Length)

[problemUrl]: https://atcoder.jp/contests/s8pc-1/tasks/s8pc_1_e E869120王国では, $ N $個の街があり, 街$ i-1 $と街$ i $は道路で結ばれている。 また, 街$ i $ $ (1≦i≦N) $には整数$ a_i $が書かれており, 道路の長さは次の規則に従って定められる。 - 街$ i-1 $と街$ i $を結ぶ道路の長さは$ a_{i-1} $$ a_i $である。 E869120王国に住むsquare1001は, 散歩をすることにした。 square1001は街$ 1 $に住んでいて, $ 1-\ >\ c_1-\ >\ c_2-\ >\ ...\ -\ >\ c_Q-\ >\ 1 $というように散歩することになっている。 しかし, square1001はとんでもない距離を歩くかもしれないので, あなたはsquare1001のために歩く距離を教えてほしい。 square1001の歩く距離を$ mod $ $ 1,000,000,007 $で求めなさい。

入力は以下の形式で与えられる。 > $ N $ $ Q $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ c_1 $ $ c_2 $ $ ... $ $ c_Q $ - $ 1 $行目には街の数$ N $, 経由地の数$ Q $が空白区切りで与えられる。 - $ 2 $行目には街に書かれている整数$ a_1,a_2,...a_N $が空白区切りで与えられる。 - $ 3 $行目にはsquare1001の散歩する経路を表す整数$ c_1,c_2,...c_Q $が空白区切りで与えられる。

出力は以下の形式に従うこと。 $ 1 $行目に, square1001が歩く距離を$ 1,000,000,007 $で割った余りを出力しなさい。ただし, 出力の末尾には改行を入れること。

### 制約 - $ 2≦N≦120,000 $ - $ 1≦Q≦120,000 $ - $ 0≦a_i≦1,000,000,000 $ - $ 1≦c_i≦N $ - $ c_{i-1}≠c_i $ - $ a_i=0⇒a_{i+1}≠0 $ ### 部分点 「$ 1≦N≦1,000 $かつ$ 1≦Q≦1,000 $かつ$ 1≦a_i≦1,000 $」を満たすテストケースに正答した場合は部分点として15点が与えられる。 「$ 1≦N≦1,000 $かつ$ 1≦Q≦1,000 $」を満たすテストケースに正答した場合は部分点として50点が与えられる。 すべてのテストケースに正答した場合は100点が与えられる。 ### Sample Explanation 1 \- $ 1 $回目に, 街$ 1 $->街$ 3 $まで行くので, $ 5^3+3^1=128 $歩く。 - $ 2 $回目に, 街$ 3 $->街$ 2 $まで行くので, $ 3^1=3 $歩く。 - $ 3 $回目に, 街$ 2 $->街$ 4 $まで行くので, $ 3^1+1^2=4 $歩く。 - $ 4 $回目に, 街$ 4 $->街$ 1 $まで行くので, $ 1^2+3^1+5^3=129 $歩く。 - よって, square1001は合計で$ 264 $歩くことになる。 ### Sample Explanation 2 square1001は$ 43,829,259,183,601,346 $歩くことになるので, それを$ 1,000,000,007 $で割った余りである$ 876,796,540 $を出力する。 ### Sample Explanation 3 square1001はどのくらい歩けばよいのでしょうか???