Bayraqlar

Стяг n şaquli zolaqdan ibarətdir və bu zolaqlar ağ, qırmızı və mavi rənglərdədir. Yanaşı zolaqlar eyni rəngdə ola bilməz və mavi zolaq həmişə qırmızı və ağ və ya ağ və qırmızı zolaqlar arasında yerləşməlidir. n zolaqlı stəyi neçə fərqli üsulla rəngləmək olar?

Giriş məlumatları

Stəyin üzərindəki zolaqların sayı n (1 ≤ n ≤ 10^6).

Çıxış məlumatları

n zolaqlı stəyi rəngləmək üçün neçə fərqli üsul olduğunu hesablayın və nəticəni 10^9 + 7 moduluna görə çıxış edin.

Nümunələr