Cho số nguyên dương \(n\). Hãy tính tổng của n số fibo đầu tiên. Vì kết quả có thể rất lớn nê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ố nguyên dương là kết quả theo modulo \(10^9+7\).

Ví dụ:

Input

3

Output

4

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

• Ví dụ Input:

  3

  • Giải thích: Tổng của ba số Fibonacci đầu tiên (0, 1, 1) là 2, nhưng tính từ 1 đến n thì tổng là 4.

• Ví dụ Output:

  4

  • Giải thích: Kết quả 4 là tổng của ba số Fibonacci đầu tiên theo yêu cầu.
    

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