Category
Similar Problems

0240. Ketma-ketlik

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^6)$.

Chiquvchi ma’lumotlar: Bitta sonni masalaning javobini chiqaring.

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