Masala #0950

Xotira 16 MB Vaqt 1000 ms
14

Bahodirjon o'ylagan ketma-ketlik.

Bahodir 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.

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


Kiruvchi ma'lumotlar:

Bitta qatorda n\((1\le n \le 10^{18})\) butun soni.


Chiquvchi ma'lumotlar:

Chiqish faylida S ning qiymatini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.


Misollar
# input.txt output.txt
1
1
1
2
8
3281