题目背景

或许是后户之国轻易不与外界联系，或许是神职所限，又或许是性格喜好的原因，摩多罗作为最初建立幻想乡的几位贤者之一，和其他贤者之间的联系并不频繁。其他如八云紫、茨木华扇等贤者均亲身走在幻想乡之中，而摩多罗却置身之外。

耗费神力发动全幻想乡级别的异变，看似规模宏大，其实并未对幻想乡造成真正的伤害，只是让一群笨蛋妖精狂躁了些而已。

谁也不知道门后的秘神心中真正的想法。

题目描述

给定一场长度为 $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$ 的结果。

输入格式

第一行三个整数 $n,m,t$。

接下来一行 $n$ 个整数 $a_1,a_2,\cdots a_n$，含义如题面中所述。

接下来一行 $m$ 个整数 $b_1,b_2,\cdots b_m$，含义如题面中所述。

输出格式

输出一行，表示构造出的 $B$ 矩阵的 $f(B)$ 的值模 $10^9+7$ 的结果。

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

提示

样例解释 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$。保证数据有解。