Matrix Construction Minimization

You are given two sequences of positive integers. The first sequence a has length n and the second sequence b has length m. Define an n-by-m matrix \(A\) where each entry is given by \(A_{i,j} = a_i \times b_j\). Your task is to construct an \((n+1)\)-by-t matrix \(B\) with positive integers satisfying the following conditions:

• Every element \(B_{i,j}\) lies in the range \([1, m]\).
• In every row of \(B\), the \(t\) elements are pairwise distinct.
• In every column of \(B\), any two adjacent entries are different, i.e. \(B_{i,j} \neq B_{i+1,j}\) for every valid \(i\) and \(j\).

Let the cost function \(f(B)\) be defined as follows: \[ f(B) = \sum_{i=1}^{n} \sum_{j=1}^{t} \; \sum_{k=\min(B_{i,j},B_{i+1,j})}^{\max(B_{i,j},B_{i+1,j})} A_{i,k} \quad \text{.} \]

Your goal is to construct a matrix \(B\) satisfying the above conditions and minimize \(f(B)\). Output the value of \(f(B)\) modulo \(10^9+7\).

Hint: It turns out that with a careful construction the problem can be reduced to choosing a permutation of t numbers (from \(1\) to \(m\)) for the first row of \(B\). For each chosen value \(x\), one can set the remaining entries in its column alternately to \(x\) and \(x+1\) (or \(x-1\) when \(x = m\)) so that the adjacent entries differ and the row uniqueness is maintained. The cost contributed by column with value \(x\) (if \(x < m\)) becomes \[ F(x)=b_x+b_{x+1}, \quad \text{and if } x=m, \; F(m)=b_{m-1}+b_m. \] Thus the overall cost is \[ f(B)=\Bigl(\sum_{i=1}^{n}a_i\Bigr)\times \Bigl(\sum_{\text{each chosen } x}F(x)\Bigr) \pmod{10^9+7}. \] To minimize \(f(B)\), you need to choose \(t\) distinct numbers \(x\) from \(\{1,2,\ldots,m\}\) with the smallest possible \(F(x)\, .\)

inputFormat

The first line contains three space-separated integers \(n\), \(m\) and \(t\) (with \(t \le m\)).

The second line contains \(n\) space-separated positive integers representing the sequence \(a\).

The third line contains \(m\) space-separated positive integers representing the sequence \(b\>.

outputFormat

Output a single integer: the minimum possible value of \(f(B)\) modulo \(10^9+7\).

sample

2 3 2
1 2
1 2 3

24