Problem C
Fibs og Dibs

Mynd fengin af flickr.com

Í hverri umferð byrjar Dagur á því að segja ,,Fibs“, þá leggja þeir tölurnar sínar saman og Dagur skiptir út gömlu tölunni sinni fyrir þessa nýju, þannig $a$ tekur gildi $a+b$. Síðan segir Elvar ,,Dibs“ og gera þeir þá sömu skref aftur nema Elvar skiptir út sinni tölu fyrir nýju, þannig $b$ tekur gildi $a+b$.

Þar sem þeir hafa ekki þolinmæðina til að spila $n$ umferðir, því þeir vilja drífa sig í uppáhaldsleikinn sinn Dibs og Fibs, þá biðja þeir þig um að hjálpa sér að finna út hvaða tölur þeir enda með eftir $n$ umferðir.

Inntak

Fyrsta línan í inntakinu inniheldur tvær heiltölur, $a$, talan sem Dagur velur, og $b$, talan sem Elvar velur. Síðan kemur ein heiltala $n$, fjöldi umferða sem þeir munu spila.

Úttak

Skrifið út hvaða tvær tölur þeir enda með eftir $n$ umferðir í leiknum. Skrifið út tölurnar tvær á einni línu, fyrst töluna hans Dags og svo töluna hans Elvars, aðskilnar með bili. Þar sem tölurnar geta orðið stórar, þá skuluð þið skrifa þær módúlus ${10}^9+7$.

Stigagjöf

2 2
2

10 16

1 2
10

17711 28657