Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: tetrahedron.in

Rezultatų failas: tetrahedron.out

Jei norite pateikti savo sprendimą - prisijunkite.

Tetraedras

Duotas tetraedras ABCD.

Skruzdėlė stovi viršūnėje D. Skruzdėlė negali nustovėti vietoje. Kiekvieną dieną ji pereina per kraštinę iš vienos viršūnės į kitą. Užduotis yra suskaičiuoti, kiek yra skirtingų n dienų kelionių, kurios prasideda ir baigiasi viršūnėje D.

Pradiniai duomenys

Vienintelėje eilutėje yra dienų skaičius n (1\\leqn\\leq10^{18}).

Rezutatai

Tegu N yra kiekis kelionių, trunkančių n dienų, kurios prasideda ir baigiasi viršūnėje D. Išveskite liekaną N dalijant iš 1000000007 (10^9+7).

Pavyzdys

Duomenys Rezultatai 
2
 
3
 
3
 
6