PRA7: Save the Green. Make Less Cuts. // Advanced

The lumberjack company gives a wooden board composed of M X N wooden square pieces to Barbara and asks her to find the minimal cost of cutting the board into square wooden pieces. Barbara can cut the board along horizontal and vertical lines, and each cut divides the board in smaller parts. Each cut has a cost depending on whether the cut is made along a horizontal or a vertical line.

Let us denote the costs of cutting it along consecutive vertical lines with x1, x2, ..., xn-1, and the cost of cutting it along horizontal lines with y1, y2, ..., ym-1. If a cut (of cost c) is made and it passes through n segments, then total cost of this cut will be n*c.

The cost of cutting the whole board into single squares is the sum of the cost of each cut made to turn the whole board into square wooden pieces of size 1x1. Barbara should compute this minimal cost of breaking the whole wooden board into these 1x1 squares.Barbara needs your help to find the minimal cost. Can you help her with this challenge?

Input Format

The first line contains two positive integers M and N, such that 2 <= M,N <= 100, separated by a single space. In the next line, there are integers y1, y2, ..., ym-1, separated by spaces. Following them are integers x1, x2, ..., xn-1, separated by spaces.

Sample Input

2 2
2
1

Output Format

Write an integer in separate line which denotes the minimal cost of cutting the whole wooden board into single wooden squares. Since the answer can be very large, output the answer modulo 10^9+7.

Sample Output

4