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~.
~2 \leq M \leq N \leq 10^6~
~1 \leq a_i \leq 10^3~
Subtask 1 [10%]
~2 \leq N \leq 3 \times 10^3~
Subtask 2 [40%]
~M = 2~
Subtask 2 [50%]
No additional constraints. This batch will only run if subtask ~1~ and subtask ~2~ are successfully completed.
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 \leq i < N)~.
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
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