← 返回题目列表

AtCoder · s8pc_1_e

E. 散歩(E869120和路径长度)

中文机器翻译题面 查看原题

問題文

在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上走多远???