Background

Perhaps because the Land of the Back Door rarely contacts the outside world, perhaps due to limits of her divine duties, or perhaps simply because of personal preference, as one of the sages who first built Gensokyo, Matara does not interact frequently with the other sages. Other sages such as Yakumo Yukari and Ibaraki Kasen all walk within Gensokyo in person, but Matara stays outside it.

Spending divine power to trigger an incident on the scale of the whole Gensokyo may look huge, but in fact it caused no real damage to Gensokyo, only making a group of foolish fairies more irritable.

No one knows what the secret god behind the door is truly thinking.

Problem Description

You are given a positive integer sequence $a$ of length $n$ and a positive integer sequence $b$ of length $m$.

Now Lan constructs an $n$-row, $m$-column positive integer matrix $A$ from sequences $a$ and $b$, satisfying $A_{i,j}=a_ib_j$. You need to construct a positive integer matrix $B$ with $(n+1)$ rows and $t$ columns, satisfying the following conditions:

• Each element of the matrix is in $[1,m]$.
• Elements in the same row of the matrix are pairwise distinct.
• Adjacent elements in each column of the matrix are different.
• Among all matrices that satisfy the above three requirements, minimize:

$$f(B)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{t}\sum\limits_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})}A_{i,k}$$

Output the value of $f(B)$ modulo $10^9+7$ for the constructed matrix $B$.

Input Format

The first line contains three integers $n,m,t$.

The next line contains $n$ integers $a_1,a_2,\cdots a_n$, as described in the statement.

The next line contains $m$ integers $b_1,b_2,\cdots b_m$, as described in the statement.

Output Format

Output one line, representing the value of $f(B)$ modulo $10^9+7$ for the constructed matrix $B$.

2 2 2
9 9
6 1

252

10 10 10
2 8 10 10 10 2 5 8 9 3
2 1 5 2 10 7 8 9 10 6

8040

Hint

Sample Explanation 1

According to the statement, we can construct $A=\begin{bmatrix}54 & 9 \\ 54 & 9 \end{bmatrix}$.

You need to construct a $(3)$-row, $(2)$-column matrix $B=\begin{bmatrix}1 & 2 \\ 2 & 1 \\ 1 & 2 \end{bmatrix}$. In this case, $f(B)=252$ is the minimum.

It can be proven that among all cases, the minimum value of $f(B)$ is $252$.

Constraints and Notes

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{Subtask} & \bm{n \le } & \bm{m \le } & \bm{t \le } & \textbf{特殊性质} & \textbf{分值}\\\hline 1 & 10 & 10 & 10 & - & 5 \\\hline 2 & 100 & 100 & 100 & - & 5 \\\hline 3 & 10^3 & 10^3 & 10^3 & - & 15 \\\hline 4 & 5\times 10^4 & 5\times 10^4 & 5\times 10^4 & - & 30 \\\hline 5 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & \textbf{A} & 10 \\\hline 6 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & \textbf{B} & 10 \\\hline 7 & 5\times 10^5 & 5\times 10^5 & 5\times 10^5 & - & 25 \\\hline \end{array}$$

• Special Property $\textbf{A}$: It is guaranteed that $a_i=1$.
• Special Property $\textbf{B}$: It is guaranteed that $m=t$.

For all testdata, it is guaranteed that $1\le a_i, b_i\le 10^9$, $1\le n, m, t\le 5\times 10^5$ and $t\le m$. It is guaranteed that a solution exists.

Translated by ChatGPT 5