Cerința

In 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 ≤ T ≤ 50, 3 ≤ N ≤ 100.000, unde T, N numere naturale
• 1 ≤ A, B ≤ 100, 1 ≤ 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

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

• ziua 3: 1 + 1*2 + 1*3 = 6 celule
• ziua 4: 2 + 1*3 + 1*6 = 11 celule
• ziua 5: 3 + 1*6 + 1*11 = 20 celule
• ziua 6: 6 + 1*11 + 1*20 = 37 celule

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

• ziua 3: 1 + 1*2 + 2*3 = 9 celule
• ziua 4: 2 + 1*3 + 2*9 = 23 celule
• ziua 5: 3 + 1*9 + 2*23 = 58 celule