Cho số nguyên dương \(n\). Tìm số fibonacci thứ \(n\). Vì n có thể rất lớn, in ra kết quả theo modulo \(10^9+7\).

INPUT FORMAT

1 dòng gồm số nguyên dương \(n(1 \leq n \leq 10^9)\).

OUTPUT FORMAT

1 dòng gồm số fibonacci thứ \(n\) theo modulo \(10^9+7\).

Ví dụ:

Input

3

Output

2

Giải thích ví dụ mẫu:

• Ví dụ Input:

  3

  • Giải thích: Số Fibonacci thứ 3 là 2, được tính từ chuỗi Fibonacci bắt đầu với 0 và 1.

• Ví dụ Output:

  2

  • Giải thích: Kết quả là 2, vì đây là số Fibonacci thứ 3.
    

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House