Tìm số Fibonacci thứ \(n\).

Dữ liệu đầu vào

• Dòng đầu tiên chứa 1 số nguyên \(n\).

Dữ liệu ra

• Một số là phần dư của kết quả tìm được khi chia cho \(10^9+7\)

Ràng buộc

• \(0 \le n \le 10^9\)

Input 1

6

Output 1

8