Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: lmio_2013_medis_vyr.in

Rezultatų failas: lmio_2013_medis_vyr.out

Jei norite pateikti savo sprendimą - prisijunkite.

Medis

Vytis gavo dovanų stebuklingą raudoną velykinį kiaušinį. Per naktį iš to kiaušinio išaugo dar stebuklingesnis velykinis medis! Jį sudaro šakos ir ant jų prisikabinę N kiaušinių, iš kurių R – raudoni (įskaičiuojant ir pradinį raudoną kiaušinį), o likę žali. Paaiškėjo, kad nauji kiaušiniai taip pat stebuklingi, ir kiekvieną tolesnę naktį iš visų raudonų kiaušinių išauga po dar tokį medį, koks išaugo iš pirmojo kiaušinio per pirmąją naktį.

Užduotis

Parašykite programą, kuri rastų, kiek raudonų ir kiek žalių kiaušinių turės medis po D dienų. Atsakymą išveskite moduliu 1000000007.

Pradiniai duomenys

Trys tarpais atskirti sveikieji skaičiai N, R ir D (2\\leqN,D\\leq10^9, 1\\leqR\\leqN).

Rezultatai

Išveskite du tarpu atskirtus skaičius – raudonų ir žalių kiaušinių skaičius po D dienų, moduliu 1000000007.

Pavyzdžiai

Pradiniai duomenys Rezultatai
5 2 2 
4 9