Masala #23PDICOHNX

Xotira 32 MB Vaqt 1000 ms

Ketma-ketlik 2

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.

Kiruvchi ma'lumotlar:

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

Chiquvchi ma'lumotlar:

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

Misollar

#	input.txt	output.txt
1	2	3
2	4	68