~11~ số Fibonacci đầu tiên gồm: ~f_0 = 0, f_1 = 1, f_2 = 1, f_3 = 2, f_4 = 3, f_5 = 5, f_6 = 8, f_7 = 13, f_8 = 21, f_9 = 34, f_{10} = 55~

Hãy viết chương trình tìm phần tử thứ ~n~ của dãy trên.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~n~ thỏa ~0 \le N \le 10^{18}~.

Output

In kết quả cần tính vì số lớn nên chia kết quả cho ~10^9 + 7~.

Samples

Sample Input 1

10

Sample Output 1

55