Masala #0223

Xotira 16 MB Vaqt 1000 ms
14

Rekkurent Formlula

Matematikada ko’pchiligingiz rekurrent formula haqida eshitgan bo’lsangiz kerak. Rekurrent formulada berilan ketma-ketlikning elementi uning boshqa elementlariga bog’liq bo’ladi. Hozirgi masalada ham rekurrent formula bilan ketma-ketlik berilgan.

\(A_{n+3}-6*A_{n+2}+11*A_{n+1}-6*A_{n}=0\)

\(A_1=3, A_2=15, A_3=41;\)

Sizning vazifangiz ketma-ketlikning \(A_n\) hadini \(10^9+7\) ga bo’lgndagi qoldiqni chiqarishingiz kerak.


Kiruvchi ma'lumotlar:

Bitta \(n\) butun son \(1 \le n \le 10^{15}\)


Chiquvchi ma'lumotlar:

\(A_n\) ketma-ketlikni hadi


Misollar
# input.txt output.txt
1
4
99
2
10
24795