0.Tính tổng dãy fibonacci

Submit solution
Points: 4 (partial)
Time limit: 1.0s
Memory limit: 98M
Author:
themiscscvn
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Số Fibonacci được xác định bởi công thức sau:

f[1] = 1.

f[2] = 1.

f[n] = f[n-1] + f[n-2].

Tìm tổng của n số fibonacci đầu tiên.

Input

Một dòng duy nhất chứa số nguyên dương n (n <= \(10^9\)).

Output

Tổng của dãy n số fibonacci đầu tiên (lấy dư cho 1000000009).

Test 1:

Input:

5

Output:

12

Test 2:

Input:

100

Output:

724844561

Comments


  • 4
    kengaming123vn  commented on March 9, 2019, 1:01 p.m.

    ai chạy đc 100% trong 0,1 s ko dạy tui với


  • -3
    vtn  commented on Dec. 24, 2018, 6:34 p.m.

    lấy dư cho 10^9 thì đã ez hơn bao nhiêu r


    • 3
      I_love_NguyenLinh  commented on Dec. 25, 2018, 1:15 p.m.

      vấn đề ko nằm ở mod mà là n <= 10^9 ...


      • -8
        vtn  commented on Dec. 25, 2018, 2:47 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.