Với ba dãy số \((a), (b), (c)\) lần lượt có \(m, n, p\) phần tử, đều bắt đầu từ chỉ số \(1\), ta định nghĩa biểu thức sau:

\[~Q(a, b, c) = \displaystyle\sum_{i = 1}^{m}\displaystyle\sum_{j = 1}^{n}\displaystyle\sum_{k = 1}^{p} max\{i, j, k\}*a_ib_jc_k~ = \sum_{\substack{1 \le i \le m\\ 1 \le j \le n\\ 1 \le k \le p}} max\{i, j, k\}*a_ib_jc_k~\]

(Dấu nhân được lược bỏ để biểu thức ngắn gọn)

Ví dụ với \(m = 2, n = 3, p = 1\):

\(Q(a, b, c) = max\{1, 1, 1\}*a_1b_1c_1 + max\{1, 2, 1\}*a_1b_2c_1 + max\{1, 3, 1\}*a_1b_3c_1 + max\{2, 1, 1\}*a_2b_1c_1 + max\{2, 2, 1\}*a_2b_2c_1 + max\{2, 3, 1\}*a_2b_3c_1\)

\(= a_1b_1c_1 + 2a_1b_2c_1 + 3a_1b_3c_1 + 2a_2b_1c_1 + 2a_2b_2c_1 + 3a_2b_3c_1\) \((*)\).

Với ba dãy \((a), (b), (c)\) được nhập vào, bạn hãy tính phần dư (không âm) của \(Q(a, b, c)\) khi chia cho \(10^9 + 7\).

Ghi chú: Với \(L\) nguyên, \(p\) nguyên dương thì số dư không âm của \(L\) chia số \(p\) có thể được tính như sau: \((L\%p + p)\%p\) với \(\%\) là phép toán lấy dư.

Đầu vào

Dòng đầu tiên chứa ba số nguyên dương \(m, n, p\) \((1 \le m, n, p \le 10^5)\).

Dòng tiếp theo chứa \(m\) số tự nhiên trong khoảng \([-10^{18}, 10^{18}]\) là các phần tử của dãy \((a)\).

Dòng tiếp theo chứa \(n\) số tự nhiên trong khoảng \([-10^{18}, 10^{18}]\) là các phần tử của dãy \((b)\).

Dòng cuối cùng chứa \(p\) số tự nhiên trong khoảng \([-10^{18}, 10^{18}]\) là các phần tử của dãy \((c)\).

Đầu ra

Một số tự nhiên duy nhất là kết quả của bài toán.

Subtask

\(30\%\) số test có \(m*n*p \le 10^6\).

Ví dụ

Đầu vào:

2 3 1
1 2
1 2 3
1

Đầu ra:

44

Giải thích: Thay \(a_1 = 1, a_2 = 2, b_1 = 1, b_2 = 2, b_3 = 3, c_1 = 1\) vào công thức \((*)\) thu được kết quả là \(44\).