FIBONACCI

Dãy Fibonacci gồm các số \(f(i)\) được định nghĩa như sau:

• \(f(i) = 1\) nếu \(i \le 2\);
• \(f(i) = f(i - 1) + f(i - 2)\) nếu \(i > 2\).

Các phần tử đầu tiên của dãy Fibonacci là:

Input

Dữ liệu vào từ tệp FIBONACCI.INP, gồm một số nguyên duy nhất \(N\) \((1 \le N \le 100)\).

Output

Ghi ra tệp FIBONACCI.OUT một số nguyên duy nhất là phần dư của \(f(N)\) khi chia cho \(10^9 + 7\).

Sample Input 1

6

Sample Output 1

8

Sample Input 2

46

Sample Output 2

836311896

Subtasks

• \(80\%\) số điểm: \(N \le 50\).
• \(20\%\) số điểm còn lại: không có ràng buộc bổ sung.