# Payroll

Time Limit : 2 sec, Memory Limit : 262144 KB

# vZ

objЂł $0$ $N-1$ ID 蓖Ăꂽ $N$ l̏]ƈĂB܂A$0$ $N-1$ ID 蓖Ăꂽ $N$ ̎dAd $j$ ɂ鎞Ԃ $t_j$łB

objЂł́A]ƈɂ葽̎doĂ炤߁Aȉ̋KŎd̊蓖ĂύXĂB

• $0$ ƂāA$d$ ڂɎd $j$ ]ƈ$(j+d)$ % $N$ Ɋ蓖ĂBŁA$p$ % $q$ $p$ $q$ Ŋ]\B

objЂ͎̋ɉēŎxB $a$ ̏]ƈd $j$ s $a \times t_j$ ~̋B]ƈ $i$ ̍ŏ̎ $s_i$~A]ƈ̃x[Vグ邽߁Aj[Nȕ@ŋオBobjЂ̏\ɂ $0$ $M-1$ ̔ԍtꂽW $f_k$ĂAl̏]ƈ̎ȉ̋Kŏ㏸B

• $0$ ƂāA$d$ ڂI_ŁA]ƈ $d$ % $N$ ̎ $f$($d$ % $M$)~㏸BAŝ͓xꂽłB

objЂ̌oSł邠Ȃ́A $D$ ̋̑zvZȂ΂ȂȂB

e]ƈ̍ŏ̎Aedɂ鎞ԁA\̓eA͂ƂȂz߂vO쐬BA͔ɑ傫Ȃꍇ̂ŁA$1000000007 (=10^9+7)$Ŋ]o͂B

͈͂ȉ̌ŗ^B

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


Psڂɏ]ƈ̐lƎď\$N$ ($1 \leq N \leq 100$)AW̌$M$ ($1 \leq M \leq 100$jA$D$ ($1 \leq D \leq 10^{15}$)^BA$N+M$100ȉłBQsڂɊe]ƈ̍ŏ̎$s_i$ ($1 \leq s_i \leq 10^8$)ŗ^BRsڂɊedɂ鎞$t_j$ ($1 \leq t_j \leq 10^8$)ŗ^BSsڂɏ\ eW$f_k$ ($1 \leq f_k \leq 10^8$)ŗ^B

̑zPsɏo͂B

## ͗P

3 2 2
3 2 1
1 2 3
1 2


## o͗P

26


## ͗Q

3 2 5
3 2 1
1 2 3
1 2


## o͗Q

91