Problema 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 + a × y + b × z 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, unde T este un număr natural
• 3 ≤ N ≤ 100.000, unde N este un număr natural
• 1 ≤ A, B ≤ 100, unde A, B sunt numere naturale
• 1 ≤ U, V, W < K, unde U, V, W sunt numere naturale
• K = 10.000.007
• Prima zi se consideră ziua 0

Exemplu