给定一场长度为 $n$ 的正整数序列 $a$ 和一个长度为 $m$ 的正整数序列 $b$。
现在蓝根据序列 $a$ 与序列 $b$ 构造了一个 $n$ 行 $m$ 列的正整数矩阵 $A$ 满足 $A_{i,j}=a_ib_j$，你需要构造 $n+1$ 行 $t$ 列的正整数矩阵 $B$ 满足以下条件：
- 矩阵的每个元素取值在 $[1,m]$ 间；
- 矩阵同一行的元素**两两**不相同；
- 矩阵的每列**相邻元素**不同；
- 在所有满足上面三项要求的矩阵中**最小化**下式：
$$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}$$
请输出构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。
## Input
第一行三个整数 $n,m,t$。
接下来一行 $n$ 个整数 $a_1,a_2,\cdots a_n$，含义如题面中所述。
接下来一行 $m$ 个整数 $b_1,b_2,\cdots b_m$，含义如题面中所述。
## Output
输出一行，表示构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。
[samples]
## Background
或许是后户之国轻易不与外界联系，或许是神职所限，又或许是性格喜好的原因，摩多罗作为最初建立幻想乡的几位贤者之一，和其他贤者之间的联系并不频繁。其他如八云紫、茨木华扇等贤者均亲身走在幻想乡之中，而摩多罗却置身之外。
耗费神力发动全幻想乡级别的异变，看似规模宏大，其实并未对幻想乡造成真正的伤害，只是让一群笨蛋妖精狂躁了些而已。
谁也不知道门后的秘神心中真正的想法。
## Note
### 样例解释 1
根据题意，可以构造出矩阵 $A=\begin{bmatrix}54 & 9 \\ 54 & 9 \end{bmatrix}$。
你需要构造出的 $3$ 行 $2$ 列的矩阵 $B=\begin{bmatrix}1 & 2 \\ 2 & 1 \\ 1 & 2 \end{bmatrix}$，此时 $f(B)=252$ 为最小值
可以证明 $f(B)=252$ 为所有情况中，$f(B)$ 的最小值。
### 数据范围及约定
$$
\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}$$
- **特殊性质** $\textbf{A}$：保证 $a_i=1$；
- **特殊性质** $\textbf{B}$：保证 $m=t$。
对于全部数据，保证 $1\le a_i, b_i\le 10^9$，$1\le n, m, t\le 5\times 10^5 $，$t\le m$。保证数据有解。