008 - 給料計算

ＰＣＫ社では $0$ から $N-1$ の ID が割り当てられた $N$ 人の従業員が働いている。また、$0$ から $N-1$ の ID が割り当てられた $N$ 個の仕事があり、仕事 $j$ にかかる時間は $t_j$である。

ＰＣＫ社では、従業員により多くの仕事を覚えてもらうため、以下の規則で仕事の割り当てを変更している。

• 初日を $0$ として、$d$ 日目に仕事 $j$ が従業員$(j+d) \% N$ に割り当てられる。ここで、$p \% q$ は $p$ を $q$ で割った余りを表す。

ＰＣＫ社の給料は時給に応じて日当で支払われる。時給が $a$ の従業員が仕事 $j$ を行うと $a \times t_j$ 円の給料が発生する。従業員 $i$ の最初の時給は $s_i$円だが、従業員のモチベーションを上げるため、ユニークな方法で給料が上がる。ＰＣＫ社の昇給表には $0$ から $M-1$ の番号が付けられた係数 $f_k$が書かれており、毎日ある一人の従業員の時給が以下の規則で上昇する。

• 初日を $0$ として、$d$ 日目が終了した時点で、従業員 $d \% N$ の時給が $f_{(d \% M)}$円上昇する。ただし、昇給が行われるのは日当が支払われた後である。

ＰＣＫ社の経理担当であるあなたは、初日から $D$ 日分の給料の総額を計算しなければならない。

各従業員の最初の時給、各仕事にかかる時間、昇給表の内容、日数を入力とし、給料の総額を求めるプログラムを作成せよ。ただし、答えは非常に大きくなる場合があるので、$1000000007 (=10^9+7)$で割った余りを出力せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$ $D$
$s_0$ $s_1$ $...$ $s_{N-1}$
$t_0$ $t_1$ $...$ $t_{N-1}$
$f_0$ $f_1$ $...$ $f_{M-1}$

１行目に従業員の人数と仕事の個数を表す数$N$ ($1 \leq N \leq 100$)、係数の個数$M$ ($1 \leq M \leq 100$）、日数$D$ ($1 \leq D \leq 10^{15}$)が与えられる。ただし、$N+M$は100以下である。２行目に各従業員の最初の時給$s_i$ ($1 \leq s_i \leq 10^8$)が整数で与えられる。３行目に各仕事にかかる時間$t_j$ ($1 \leq t_j \leq 10^8$)が整数で与えられる。４行目に昇給表の 各係数$f_k$ ($1 \leq f_k \leq 10^8$)が整数で与えられる。

出力

給料の総額を１行に出力する。

入出力例

入力例１

3 2 2
3 2 1
1 2 3
1 2

出力例１

26

入力例２

3 2 5
3 2 1
1 2 3
1 2

出力例２

91