Masala #23PDICOHNX

Sizga quyidagicha ketma-ketlik betilgan:

$a_1=1$

$a_2=3$

$...$

$a_n=4a_{n-1}-4a_{n-2}+2^n$

Sizga $n$ butun soni berilgan. Siz $a_n$ ning qiymatini $10^9+7$ ga bo'lgandagi qoldiqni chop etishingiz kerak bo'ladi.

Yagona qatorda $n$ natural soni $n(1≤n≤10^{18}).$

Yagona qatorda masala yechimi $10^9+7$ ga bo'lgandagi qoldiqni chop eting.