abcacm

ABCacm

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:

Ş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$ si vă cere să calculaţi care este elementul al $i$-lea din şir, modulo $9907$.

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

9899