Masala B

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.

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

$a_n$ ning qiymatini $10^9+7$ ga bo’lgandagi qoldiqni chiqaring