== include(page="template/taskheader" task_id="abcacm") ==
Poveste şi cerinţă...
Lui Gigel îi place să se joace cu numere. A ales trei numere naturale $A$, $B$ şi $C$ şi cu ajutorul lor calculează un şir simpatic de numere.
Şirul simpatic incepe cu doi de $0$. Restul elementelor şirului se calculează după o regulă simplă, folosind numerele $A$, $B$ şi $C$. Elementul al i-lea (i ≥ 3) din şir se calculează astfel:
- se înmulţeşte elementul al (i-2)-lea cu A
- se înmulţeşte elementul al (i-1)-lea cu B
- se calculează suma rezultatelor de mai sus, la care se aduna C
Gigel s-a plictisit rapid să tot scrie la şir, aşa că vă cere ajutorul. El vă dă un numar natural $i$ şi vă cere să calculaţi care este elementul al $i$-lea din şir, modulo $9907$.
h2. Date de intrare
Fişierul de intrare $abcacm.in$ ...
Pe prima linie a fisierul de intrare $abcacm.in$ se găseşte numărul $T$ de teste. Pe următoarele $T$ linii se găsesc
câte $4$ numere naturale $A$, $B$, $C$ şi $i$, separate prin spaţii, cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $abcacm.out$ ...
În fişierul de ieşire $abcacm.out$ trebuie afişate $T$ linii, fiecare conţinând elementul al $i$-lea din şir, modulo $9907$, pentru testul aferent.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ A ≤ 2013$
* $1 ≤ B ≤ 2014$
* $1 ≤ C ≤ 2015$
* $1 ≤ i ≤ 2^31 - 1$
h2. Exemplu
table(example). |_. abcacm.in |_. abcacm.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
1 2 3 4
| 9
|
h3. Explicaţie
...
Şirul este $0$, $0$, $3$, $9$, $24$, $60$, etc. Al $4$-lea element este $9$, iar $9$ modulo $9907$ este $9$ (ceea ce trebuie afişat).
== include(page="template/taskfooter" task_id="abcacm") ==
