Masala #0950

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 32 %

#Matrix

#Dinamik dasturlash

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 S_n 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_n ning qiymatini \(10^9+7\) ga bo'lgandagi qoldiqni chop eting.

Misollar

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

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin