După ce a primit de la Simonet, profesorul său de studii sociale, tema pentru proiect, tânărului Trevor i-a venit ideea jocului “Pay it forward”. Pentru cei care nu știu acest joc, el constă în ajutarea de către Trevor a oamenilor aflați la ananghie. Aceștia la rândul lor vor ajuta alți oameni și așa mai departe. Fiecare participant (inclusiv Trevor) trebuie să realizeze câte k fapte bune prin care să ajute oamenii. Vârstnicii și tinerii își îndeplinesc în mod diferit această sarcină. Vârstnicii au nevoie de zv zile pentru a introduce în joc o altă persoană, iar tinerii au nevoie de zt zile. Astfel dacă un vârstnic, respectiv un tânăr, intră în joc în ziua i, el va introduce la rândul lui în joc prima persoană în ziua i+zv, respectiv în ziua i+zt tânărul, a doua persoană în ziua i+2*zv, respectiv în ziua i+2*zt tânărul și așa mai departe. Astfel numărul de persoane care participă la joc poate fi diferit în funcție de cum sunt alese persoanele vârstnice și cele tinere. Trevor dorește ca în joc să fie realizate în total cât mai multe fapte bune, dar fiecare participant să aducă în joc maximum (k+1)/2 tineri și maximum (k+1)/2 vârstnici. Participanții pot aduce mai puține persoane de un anumit tip, dar nu au voie să depășească numărul de (k+1)/2 persoane de același tip.

Cerința

Care este numărul fb de fapte bune care mai sunt de realizat, după trecerea a n zile, de către persoanele intrate deja în joc, astfel încât numărul total de fapte bune așteptate (și cele realizate și cele nerealizate) să fie maxim?

Date de intrare

Fișierul de intrare pif.in conține pe prima linie numărul natural n, pe a doua linie numărul k și pe a treia linie numerele zv și zt separate printr-un spațiu.

Date de ieșire

În fișierul de ieșire pif.out se va scrie restul împărțirii lui fb, cu semnificația din enunț, la 1234567 (fb modulo 1234567).

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• 1 ≤ k, zt, zv ≤ n
• Pentru teste în valoare de 30 de puncte fb ≤ 1.000.000
• Pentru teste în valoare de 30 de puncte zv = zt = 1
• Pentru teste în valoare de 20 de puncte zv = zt ≠ 1
• Pentru teste în valoare de 70 de puncte k•n ≤ 1.000.000
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

Exemplu:

pif.in

4
2
1 2

pif.out

7

Explicație

n = 4, k = 2, zv = 1, zt = 2. Avem 16 moduri posibile în care se pot alege persoanele vârstnice și tinere. Dintre ele doar 5 respectă condiția ca numărul vârstnicilor și al tinerilor să fie maxim 1. Dintre cele 5 doar două obțin un număr maxim de fapte bune așteptate. Notăm cu T pe Trevor, cu Vn persoanele vârstnice și cu Tn persoanele tinere. Unul dintre cele 2 cazuri cu număr maxim de fapte bune este următorul:

În zilele următoare:
V2 ar trebui să mai ajute încă un tânăr.
V3 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
T1 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
T2 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
Deci au mai rămas 7 fapte bune de realizat.
Celălalt caz cu număr maxim de fapte bune este următorul:

În zilele următoare:
V2 ar trebui să mai ajute încă un tânăr.
T1 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
T2 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
T3 ar trebui să mai ajute încă două persoane, un tânăr și un vârstnic.
În total au mai rămas 7 fapte bune de realizat.