Masala #0223

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.

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

\(A_n\) ketma-ketlikni hadi