Pandemia

Cerință

În plină perioadă de pandemie, cercetătorii unui institut vor să facă o serie de experimente pe culturi de celule. S-a observat deja că celula cercetată are o creștere liniară dependentă de cele trei zile imediat anterioare: dacă acum două zile aveam $x$ celule, ieri aveam $y$ iar astăzi avem $z$ celule, atunci mâine vom avea $x+ay+bz$ celule. Dacă într-o zi, numărul de celule depășește o valoare $k$, cercetătorii reduc cultura la valoarea modulo $K$.

Dacă, pentru un $n$ dat, se cunoaște numărul de celule din zilele $n$, $n-1$, $n-2$ și se cunosc factorii de multiplicare $a$ și $b$, care este numărul de celule care trebuie cultivate în primele $3$ zile ale experimentului?

Date de intrare

Fișierul de intrare pandemia.in conține mai multe seturi de date. Pe prima linie se va găsi un număr întreg $T$ reprezentând numărul de experimente pentru care se cere răspunsul. Pe următoarele $T$ linii se vor găsi experimentele: câte șase numere întregi separate prin spații, în ordinea următoare: $N$, $A$, $B$, $U$, $V$, $W$, unde $N$ este numărul de zile ale experimentului, $A$ și $B$ sunt factorii de multiplicare din enunț, iar $U, V$, respectiv $W$ reprezintă numărul de bacterii din zilele $N, N-1$ și, respectiv, $N-2$.

Date de ieșire

Fișierul de ieșire pandemia.out va conține $T$ linii cu răspunsurile, în ordine, la cele $T$ experimente din fișierul de intrare, și anume trei numere naturale mai mici decât $K$ separate prin câte un spațiu, reprezentând numărul de bacterii din ziua $0$, ziua $1$ și, respectiv ziua $2$ (în această ordine).

Restricții și precizări

• $1 \leq T \leq 50, 3 \leq N \leq 100 \ 000$, unde $T, N$ numere naturale
• $1 \leq A, B \leq 100, 1 \leq U, V, W < K$, unde $A$, $B$, $U$, $V$, $W$ numere naturale
• $K = 10 \ 000 \ 007$
• prima zi se consideră ziua $0$

Exemplu

pandemia.in

2
6 1 1 37 20 11
5 1 2 58 23 9

pandemia.out

1 2 3
1 2 3

Explicație

Testul $1:$ Intr-adevăr, dacă:

• ziua $0: 1$ celulă
• ziua $1: 2$ celule
• ziua $2: 3$ celule

atunci:

• ziua $3: 1 + 1 \cdot 2 + 1 \cdot 3 = 6$ celule
• ziua $4: 2 + 1 \cdot 3 + 1 \cdot 6 = 11$ celule
• ziua $5: 3 + 1 \cdot 6 + 1 \cdot 11 = 20$ celule
• ziua $6: 6 + 1 \cdot 11 + 1 \cdot 20 = 37$ celule

Testul $2:$ Intr-adevăr, dacă:

• ziua $0: 1$ celulă
• ziua $1: 2$ celule
• ziua $2: 3$ celule

atunci:

• ziua $3: 1 + 1 \cdot 2 + 2 \cdot 3 = 9$ celule
• ziua $4: 2 + 1 \cdot 3 + 2 \cdot 9 = 23$ celule
• ziua $5: 3 + 1 \cdot 9 + 2 \cdot 23 = 58$ celule