Mô tả

Tính số Fibonacci thứ $n$.

Định nghĩa: $F_1=1,\ F_2=1,\ F_n=F_{n-1}+F_{n-2}$.

Input

Số nguyên $n$ ($1 \le n \le 10^6$).

Output

In ra $F_n \bmod (10^9+7)$.