Masala #0411

Xotira 64 MB Vaqt 1000 ms
14

Habibulloh o’ylagan ketma ketlik

Habibulloh har xil ketma-ketliklarni yaxshi ko’rardi, u kunlardan bir kun bir‑biriga bog’liq bo’lgan ketma-ketlikni o’ylab topdi. Uning o’ylab topgan ketma‑ketligi quyidagicha.

Habibulloh bu ketma – ketlikning n chi hadidagi a ning qiymatini bilmoqchi, Unga buni hisoblashda yordam bering.


Kiruvchi ma'lumotlar:

Bitta qatorda \(n ( 0 \le n \le 10^{18})\) butun son


Chiquvchi ma'lumotlar:

\(a_n\) ning qiymatini \(10^9+7\) ga bo’lgandagi qoldiqni chiqaring


Misollar
# input.txt output.txt
1
1
3
2
2
10
3
3
36