Tổng trọng số 2

Điểm: 200 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Trọng số của bộ 3 có thứ tự $(x,y,z)$ bằng $(x+y)\cdot (y+z)$ nếu $max(x,z)\le 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ả bộ 3 $(a_i,b_j,c_k)$ với $1\le i\le n,1\le j\le m,1\le k\le q$

Input, Output và Subtasks

Input

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

Output

Một số nguyên là tổng trọng số tìm được sau khi $mod\ 10^9+7$

Subtasks

Subtask 1 $(12\%)$ : $n,m,q \le 20$
Subtask 2 $(28\%)$ : $n,m,q \le 1000$
Subtask 3 $(60\%)$ : Không có giới hạn gì thêm

Sample 1

Input

Output

Bình luận

Không có bình luận nào.