E - 散歩 (E869120 and Path Length) Editorial /

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はどのくらい歩けばよいのでしょうか???