Profesorul de informatică trebuie să corecteze tezele a m elevi. Elevii au avut de rezolvat n probleme în teză, numerotate de la 1 la n. Fiecare elev a rezolvat toate problemele, deci profesorul are de corectat în total m x n probleme. El observă că luând lucrările la rând și corectând toate problemele din prima lucrare, apoi toate problemele din a doua lucrare, ș.a.m.d., nu obține întotdeauna cel mai mic timp total de corectare a tezelor. Profesorul are următoarea metodă de corectură:

• Toate tezele se vor corecta în f faze (1 ≤ f ≤ n).
• În fiecare fază i se va decide asupra unei submulțimi de probleme care nu au fost deja corectate, Si. Aceste probleme se vor corecta în toate tezele înainte să se revină la prima teză.
• Formal, alegem Si \( \subseteq \) {1,...,n} astfel încât Si ∩ Sj = ∅, pentru orice i, j ∊ {1, ..., f}, i ≠ j și S1 ∪ ... ∪ Sf = {1, ..., n}

La începerea corectării fiecărei teze, trebuie identificat numele elevului, proces care durează exact p secunde de fiecare dată, chiar dacă se revine la aceeași teză de mai multe ori.

După începerea corectării unei teze, căutarea fiecărei probleme durează k secunde. Corectarea primei probleme din submulțimea aleasă durează t[1] secunde, corectarea celei de-a doua probleme durează t[2] secunde ș.a.m.d. Se garantează că t[1] < t[2] < ... < t[n]. De fiecare dată când se revine la o anumită teză și se reîncepe corectarea ei cu o altă submulțime de probleme, corectarea primei probleme din submulțime va dura din nou t[1] secunde.

Valoarea t[1] va fi dată în fișierul de intrare împreună cu valorile d[0], ..., d[q-1], din care se vor obține celelalte valori din șirul t prin formula: t[i] = t[i-1] + d[i % q], pentru orice i ∊ {2, ..., n}, unde x % y semnifică restul împărțirii lui x la y.

Cerința

Să se determine timpul minim în care pot fi corectate cele m lucrări.

Date de intrare

Pe prima linie a fișierului de intrare teze.in se află numerele n, m, p și k, despărțite prin câte un spațiu. Pe a doua linie se află două valori t1 și q, despărțite printr-un spațiu. Pe următoarele q linii se află valorile d[0], ..., d[q-1].

Date de ieșire

În fișierul de ieșire teze.out se va scrie un singur număr, reprezentând numărul de secunde în care se pot corecta tezele modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1.500.000.000, unde n este numărul problemelor din teze
• 1 ≤ m, q, k ≤ 1000, unde m este numărul elevilor, q este lungimea șirului d, iar k reprezintă numărul de secunde necesar căutării unei probleme
• 1 ≤ p ≤ 1010, unde p este numărul de secunde necesar identificării numelui unui elev
• 1 ≤ t[1], d[i] ≤ 10
• Pentru 5 puncte, n ≤ 25
• Pentru 10 puncte, n ≤ 50
• Pentru 20 de puncte, n ≤ 10000
• Pentru 30 de puncte, n ≤ 10.000.000
• Pentru 7 puncte, q = 1
• Pentru 8 puncte, q = 2
• Pentru 20 de puncte, fără alte restricții suplimentare

Exemplu:

teze.in

2 10 5 2
1 1 
2

teze.out

130

Explicație

Avem două probleme în teză, iar t[1] = 1, t[2] = t[1] + d[0] = 1 + 2 = 3. Dacă le corectăm împreună, timpul de corectare pentru fiecare teză va fi: 5 secunde pentru găsirea numelui elevului, 2 secunde pentru găsirea primei probleme, 1 secundă pentru corectarea primei probleme, 2 secunde pentru găsirea problemei a doua și 3 secunde pentru corectarea problemei a doua, deci în total 5 + 2 + 1 + 2 + 3 = 13 secunde pentru fiecare dintre cele 10 teze, adică 130 de secunde în total.

O altă posibilitate este să corectăm prima dată problema 1 în toate tezele, iar pe urmă să corectăm problema 2 în toate tezele. Pentru corectarea primei probleme avem: 5 secunde începerea corectării, 2 secunde găsirea problemei și 1 secundă corectarea problemei, în total 5 + 2 + 1 = 8 pentru o teză, în total 80 de secunde pentru toate tezele. Pentru corectarea problemei 2 avem exact același calcul, rezultă în total 160 de secunde, deci prima metodă a fost mai eficientă și posibilitate mai bună nu există.