Trọng số của bộ ba có thứ tự ~(x, y, z)~ bằng ~(x + y) × (y + z)~ nếu ~max(x, z) ≤ y~; hoặc bằng ~0~ nếu ~max(x, z) > y~.

Cho ba dãy số nguyên dương ~a = a_1, a_2, \dots , a_n,\ b = b_1, b_2, \dots , b_m,\ c = c_1, c_2, \dots , c_q~. Hãy tính tổng trọng số của tất cả các bộ ba ~(a_i , b_j , c_k)~ với ~1 ≤ i ≤ n,\ 1 ≤ j ≤ m,\ 1 ≤ k ≤ q~.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n, m, q~;
• Dòng thứ hai chứa ~n~ số nguyên dương: ~a_1, a_2, \dots, a_n\ (a_i ≤ 10^9)~;
• Dòng thứ ba chứa ~m~ số nguyên dương: ~b_1, b_2, \dots , b_m\ (b_i ≤ 10^9)~;
• Dòng thứ tư chứa ~q~ số nguyên dương: ~c_1, c_2, \dots , c_q\ (c_i ≤ 10^9)~.

Output

• Ghi một số nguyên là tổng trọng số sau khi chia lấy dư cho ~1000000007~.

Scoring

• 12% số điểm của bài có ~n \leq 20~.
• 28% số điểm của bài có ~n \leq 1000~.
• 60% số điểm của bài có ~n \leq 10^5~.

Sample Input

4 3 5
1 4 2 3
4 6 1
6 3 2 4 2

Sample Output

2300