Răcituri cu pireu

Teo se duce la cantina lui favorită (cea de la ASE) ca să guste din noua gamă de alimente - răcituri cu pireu.

La bufetul de răcituri, el are la alegere $R$ tipuri de răcituri. Al $i$-lea tip ($0 ≤ i < R$) costă $r_i$ lei. Pentru fiecare tip de răcitură, Teo, cu o probabilitate de $\frac{1}{2}$, își pune în farfurie o răcitură.

La bufetul de pireu, el are la alegere $P$ tipuri de pireu. Pireul se vinde la volum, așa că pentru al $i$-lea tip de pireu ($0 ≤ i < P$), Teo se poate servi cu pireu în valoare de $0$, $1$, ..., $p_i$ lei. Pentru fiecare tip de pireu, Teo se servește uniform aleatoriu cu o cantitate permisă de pireu.

Cantina oferă următoarea reducere: dacă prețul total al alimentelor alese de Teo este strict mai mare decât suma de $X$ lei, atunci Teo primește o reducere de $50\%$.

Cerință

Care este, în medie, prețul plătit de Teo?

Date de intrare

Pe prima linie din standard input se află numerele $R$, $P$ și $X$ cu semnificația din enunț.

Pe a doua linie se află $R$ numere întregi: $r_0, r_1, \dots, r_{R−1}$.

Pe a treia linie se află $P$ numere întregi: $p_0, p_1, \dots , p_{P − 1}$.

Date de ieșire

Pe singura linie din standard output afișați răspunsul, modulo $10^9 + 7$.

Dacă răspunsul este egal cu fracția $\frac{A}{B}$, afișați numărul $A \cdot B^{−1}$ (modulo $10^9 + 7$).

Restricții și precizări

• $1 \leq P, R \leq 100$
• $1 \leq p_i, r_i \leq 10^3$
• $1 \leq X \leq 2 \cdot 10^5$
• În secțiunea „Atașamente” din dreapta paginii, puteți descărca un fișier C++ care implementează operații de bază ale aritmeticii modulare. Acesta este util mai ales dacă nu ați mai lucrat cu noțiunea de invers modular.
• Teo știe că forma corectă este piure dar din motive de marketing cantina continuă cu denumirea de pireu.

Exemplul 1

stdin

5 3 10
2 7 6 2 6
6 7 10

stdout

142806425

Exemplul 2

stdin

10 10 100
26 27 72 11 6 30 60 90 28 15
60 68 38 48 22 65 19 75 17 1

stdout

413422235