Two integer sequences, A and B, each of the same length L, are given to you in run-length encoded (RLE) form: sequence A is described by k1 runs (value, count) listed in order (the first run covers positions 1..count1, the next covers the following count2 positions, and so on), and sequence B similarly by k2 runs. The counts of A's runs sum to exactly L, and so do the counts of B's runs (the same L for both). You are NOT given L directly — it is implied by the runs.
Compute the dot product sum(A[i] * B[i] for i = 1..L). Since this value can be astronomically large, print it modulo 1,000,000,007. The true dot product may be negative — print the mathematically correct non-negative residue in the range [0, 1000000006] (i.e. ((x mod M) + M) mod M, not a value that can come out negative).
Input format
Line 1: two integers k1 k2 — the number of runs in A and in B.
Next k1 lines: each value count for one run of A, in order.
Next k2 lines: each value count for one run of B, in order.
Output format
A single non-negative integer: the dot product modulo 1,000,000,007.
Constraints
- 1 ≤ k1, k2 ≤ 200000
- 1 ≤ count ≤ 10^9 for every run
- -10^9 ≤ value ≤ 10^9 for every run
- the counts of A's runs sum to the same total
Las the counts of B's runs