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