Tổng ước Fibonacci

View as PDF




Authors:
Problem types
Points: 400 (p) Time limit: 1.5s Memory limit: 1G Input: stdin Output: stdout

Fibonacci là một dãy số huyền bí được phát minh ra từ xa xưa, là nghiệm của \(1\) bài toán ít người biết đến trong bộ sách … gì gì đó ko nhớ nữa :))) . Những con số đầu tiên của dãy là \((1;1;2;3;5;8; ...)\). Trinh rất thích dãy số này, và thường xuyên cho Tấn xem những gì cô mới chơi đùa được với dãy số ấy. Tấn cũng đã học về dãy số ấy và phát hiện nó có một điều gì đó rất bất bình thường. Sau một hồi khám phá, cuối cùng mọi thứ được đúc kết trong câu đố của cậu cho Trinh:

Cho \(T\) số \(n\). Với mỗi số \(n\), tìm tổng các ước số của số Fibonacci thứ \(n\) mà nó là số Fibonacci, sao cho các ước không được trùng nhau (\(2\) số \(1\) đầu dãy được tính làm \(1\)).

Trinh, dù thích câu đố này, nhưng không thể làm nó vì cô đang bận xem bóng đá Vòng Loại thứ \(3\) World Cup khu vực Châu Á (hay ít nhất là cô nói với cậu thế). Trinh nhờ các bạn giải giúp câu đố này.

Nhưng mọi chuyện vẫn chưa kết thúc tại đây. Tấn còn ác hơn khi cho các số \(n\) của cậu ẩn trong \(1\) xâu kí tự \(S\), trong đó các số \(n\) được bao giữa các dấu ngoặc tròn “( )”, và số \(T\) của cậu bị ẩn và bạn sẽ chẳng biết được số \(T\) này. Mục đích của việc này là làm cho các bạn loạn mắt lên thôi chứ chẳng có gì cả :))) Trinh “trả giá” độ khó bài này vì các bạn và cuối cùng Tấn chỉ cho thêm \(1\) cái điều kiện “giảm bớt” là: Các cặp ngoặc không lồng vào nhau, chúng độc lập với nhau và không tác động lên các cặp ngoặc kia. Trinh đành chấp nhận thử thách của cậu và nhờ các bạn. Các bạn hãy giúp Trinh nhé :( Các kết quả của cùng 1 số n in ra mỗi kết quả mỗi dòng.

Input

  • Gồm \(1\) dòng duy nhất là xâu \(S\), chứa \(T\) số \(n\) (\(T\) ẩn và \(T≤100\) cùng với các \(n≤10^{12}\)).

Output

  • Với mỗi số \(n\), mỗi dòng in \(1\) kết quả là tổng các ước số của số Fibonacci thứ n mà nó là số Fibonacci sau khi mod \(10^9+7\).

Scoring

  • Subtask \(1\) (\(25\%\) số điểm): \(n≤10^3.\)
  • Subtask \(2\) (\(25\%\) số điểm): \(n≤10^6.\)
  • Subtask \(3\) (\(25\%\) số điểm): \(n≤10^9.\)
  • Subtask \(4\) (\(25\%\) số điểm): \(n≤10^{12}.\)

Example

Test 1

Input
12345(15)12345
Output
618
Note
  • Số n tìm được là \(15\), số Fibonacci thứ \(15\)\(610\).
  • Các ước là Fibonacci của số \(610\)\(1, 2, 5, 610.\)
  • Tổng của chúng là \(1+2+5+610=618\)

Comments


  • 1
    thanphong 10:47 p.m. 12 apr, 2022

    àk rồi mik hiểu rồi

    xin lỗi cả nhà hehe

    mik chưa đọc kĩ dòng cuối

    xin lũi vì điều đó


    • 1
      thanphong 10:27 p.m. 12 apr, 2022 edit 2

      ad cho mik hỏi là test mẫu ấy

      ad có bỏ quên số 10 với số 61 không vậy, vì 10 và 61 cx là ước của 610 mak

      ad giải thích hộ mik cái


      • 1
        minhhieu2006 10:30 p.m. 10 apr, 2022

        bài này có trick gì k ạ?


        • 2
          huyhau6a2 9:53 p.m. 10 apr, 2022 edited

          đã chấm lại bài, xin lỗi các bạn huhu(lúc đầu tưởng không ai ac hóa ra sau khi xem kỹ mới thấy test sai nên có sự bất tiện này)