An Animal Contest 7 P3 - Squirrel Scramble

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

After receiving the intel from Julian (don't worry, he is completely safe), Geven now has to analyse it. Some statistics are already well known (such as squirrels being reptiles with a life span rivalling Greenland sharks). Unfortunately, due to the harrowing escape from the squirrels, some of Julian's intel is missing. Geven notices that the squirrel armada is actually formed in a line, with teleport portals along it. To procure the necessary statistics for the AAC committee, Geven must perform some complex maths involving the entity known as RNG (black magic).

There are N checkpoints connected together by N-1 paths, where the i-th path connects checkpoint i to checkpoint i+1 and requires a_i minutes to pass through. To make travelling faster, M checkpoints have portals that one can choose to take in order to arrive immediately at any other portal.

Define f(i, j) as the minimum time needed to travel from checkpoint i to j. Find the sum of f(i, j) over all (i, j) where 1 \le i < j \le N. Since this number may be extremely large, output it modulo 10^9+7.

Constraints

2 \le M \le N \le 10^6

1 \le a_i \le 10^3

Subtask 1 [10%]

2 \le N \le 3 \times 10^3

Subtask 2 [40%]

M = 2

Subtask 3 [50%]

No additional constraints. This batch will only run if subtask 1 and subtask 2 are successfully completed.

Input Specification

The first line of input contains two integers N, and M.

The second line of input contains M space separated integers, the checkpoints which have portals.

The third line of input contains N-1 space separated integers representing a_i for all i (1 \le i < N).

Output Specification

Output one integer, the minimum cost to travel from each checkpoint to every other checkpoint modulo 10^9+7.

Sample Input 1

5 2
2 5
4 6 1 7

Sample Output 1

56

Explanation for Sample Output 1

Travelling from checkpoint 1 will take 4 minutes to reach checkpoint 2, 10 minutes to reach checkpoint 3, 11 minutes to reach checkpoint 4, and 4 minutes to reach checkpoint 5.

Travelling from checkpoint 2 will take 6 minutes to reach checkpoint 3, 7 minutes to reach checkpoint 4, and 0 minutes to reach checkpoint 5.

Travelling from checkpoint 3 will take 1 minute to reach checkpoint 4, and 6 minutes to reach checkpoint 5.

Lastly, it will take 7 minutes to reach checkpoint 5 from checkpoint 4.

Adding all of these values up yields 56, the minimal amount of time required.

Sample Input 2

10 3
9 3 8
3 8 4 1 4 4 3 4 4

Sample Output 2

334

Comments

There are no comments at the moment.