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.