「Wdoi-2」禁断之门对面，是此世还是彼世

或许是后户之国轻易不与外界联系，或许是神职所限，又或许是性格喜好的原因，摩多罗作为最初建立幻想乡的几位贤者之一，和其他贤者之间的联系并不频繁。其他如八云紫、茨木华扇等贤者均亲身走在幻想乡之中，而摩多罗却置身之外。 耗费神力发动全幻想乡级别的异变，看似规模宏大，其实并未对幻想乡造成真正的伤害，只是让一群笨蛋妖精狂躁了些而已。 谁也不知道门后的秘神心中真正的想法。

给定一场长度为 $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$。保证数据有解。