## An Animal Contest 7 P3 - Squirrel Scramble

View as PDF

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 checkpoints connected together by paths, where the -th path connects checkpoint to checkpoint and requires minutes to pass through. To make travelling faster, checkpoints have portals that one can choose to take in order to arrive immediately at any other portal.

Define as the minimum time needed to travel from checkpoint to . Find the sum of over all where . Since this number may be extremely large, output it modulo .

#### Constraints

##### Subtask 2 [50%]

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

#### Input Specification

The first line of input contains two integers , and .

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

The third line of input contains space separated integers representing for all .

#### Output Specification

Output one integer, the minimum cost to travel from each checkpoint to every other checkpoint modulo .

#### Sample Input 1

5 2
2 5
4 6 1 7

#### Sample Output 1

56

#### Explanation for Sample Output 1

Travelling from checkpoint will take minutes to reach checkpoint , minutes to reach checkpoint , minutes to reach checkpoint , and minutes to reach checkpoint .

Travelling from checkpoint will take minutes to reach checkpoint , minutes to reach checkpoint , and minutes to reach checkpoint .

Travelling from checkpoint will take minute to reach checkpoint , and minutes to reach checkpoint .

Lastly, it will take minutes to reach checkpoint from checkpoint .

Adding all of these values up yields , 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