该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

斐波那契数 （通常用 $F(n)$ 表示）形成的序列称为 斐波那契数列 。该数列由 $0$ 和 $1$ 开始，后面的每一项数字都是前面两项数字的和。也就是：

$F(0) = 0，F(1) = 1$

$F(n) = F(n - 1) + F(n - 2)$，其中 $n > 1$ 给定 $n$ ，请计算 $F(n)$ 。

输入格式

输入一个整数 $n$ （$1≤n≤1000$）。

输出格式

输出一个整数，表示斐波那契数列的第 $n$ 项，答案可能很大请对 $10^9+7$取模。

样例

4

3

样例解释

对于第一个样例：

$F(4) = F(3) + F(2) = 2 + 1 = 3$