Category

Similar Problems

0241. Ketma-ketlik_2

Time limit : 1000 ms
Memory limit : 64 mb

Quyidagicha aniqlanadigan ketma-ketlik berilgan:


$$F_0 = F_1 = F_2 = 1, F_i=F_{i-3}+F_{i-2}+F_{i-1} (i >2).$$

Bu ketma-ketlikning n-hadini topuvchi dastur tuzing. Bu son juda katta bo’lishi mumkin, shuning uchun sizdan faqat uni $1000000007$ $(10^9+7)$ ga bo’lgandagi qoldiqni topish so’raladi.


Kiruvchi ma’lumotlar: Birinchi qatorda $n$ soni berilgan $(0 \le n \le 10^{18})$.


Chiquvchi ma’lumotlar: Bitta sonni masalaning javobini chiqaring.

Input
0
Output
1
Input
6
Output
17
Input
300
Output
638993329