Răcituri cu pireu

Time limit: 0.2s Memory limit: 64MB Input: Output:

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 RR tipuri de răcituri. Al ii-lea tip (0i<R0 ≤ i < R) costă rir_i lei. Pentru fiecare tip de răcitură, Teo, cu o probabilitate de 12\frac{1}{2}, își pune în farfurie o răcitură.

La bufetul de pireu, el are la alegere PP tipuri de pireu. Pireul se vinde la volum, așa că pentru al ii-lea tip de pireu (0i<P0 ≤ i < P), Teo se poate servi cu pireu în valoare de 00, 11, ..., pip_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 XX lei, atunci Teo primește o reducere de 50%50\%.

Cerință

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

Date de intrare

Pe prima linie din standard input se află numerele RR, PP și XX cu semnificația din enunț.

Pe a doua linie se află RR numere întregi: r0,r1,,rR1r_0, r_1, \dots, r_{R−1}.

Pe a treia linie se află PP numere întregi: p0,p1,,pP1p_0, p_1, \dots , p_{P − 1}.

Date de ieșire

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

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

Restricții și precizări

  • 1P,R1001 \leq P, R \leq 100
  • 1pi,ri1031 \leq p_i, r_i \leq 10^3
  • 1X21051 \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.
# Punctaj Restricții
1 20 P=0P = 0, R20R ≤ 20 și X=2105X = 2 \cdot 10^5 (niciodată nu se aplică reducerea).
2 20 P=0P = 0, R20R ≤ 20
3 20 P=0P = 0
4 20 pi5  0i<Pp_i \leq 5\ \forall\ 0 \leq i < P
5 20 Fără restricții suplimentare

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

Log in or sign up to be able to send submissions!