Time Limit: 3 sec / Memory Limit: 128 MB
問題文
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点が与えられる。
入力例1
4 3 5 3 1 2 3 2 4
出力例1
264
- 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歩くことになる。
入力例2
3 2 23 12 9 2 3
出力例2
876796540
square1001は43,829,259,183,601,346歩くことになるので, それを1,000,000,007で割った余りである876,796,540を出力する。
入力例3
2 1 1000000000 1000000000 2
出力例3
625113690
square1001はどのくらい歩けばよいのでしょうか???