Vươn tới Mặt Trăng

Submit solution
Points: 3
Time limit: 1.0s
Memory limit: 10M
Python 3 20M
Author:
CNTT2_K59
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

Mặt Trăng là vệ tinh tự nhiên duy nhất của Trái Đất và là vệ tinh tự nhiên lớn thứ năm trong Hệ Mặt Trời. Vì thế, tỉ phú Elon Musk đã xây một cầu thang siêu dài khổng lồ nối từ Trái Đất tới Mặt Trăng. Bạn hãy giúp CEO của SpaceX tính toán xem có bao nhiêu cách để leo lên Mặt Trăng bằng cầu thang bộ đó nhé. (Do số cách có thể rất lớn nên hãy trả về phân dư cho \(10^9\) + 7)

Biết rằng cầu thang bộ đó có n bậc, người tham gia leo thang chỉ có thể bước a hoặc b bậc một lúc.

Input:

3 số n, a, b. (0 ≤ n ≤ \(10^7\), 1 ≤ a, b ≤ \(10^5\)), (a != b)

Output:

Một số nguyên dương là số cách leo n bậc thang.

Example:

Input

8 2 3

Output

4

Giải thích:

Có 4 cách để leo cầu thang lên Mặt Trăng như sau:

Cách 1: 2 + 2 + 2 + 2 (Bước 2 bậc một lúc)

Cách 2: 3 + 3 + 2

Cách 3: 3 + 2 + 3

Cách 4: 2 + 3 + 3

Comments


  • 1
    TICHPX  commented on May 15, 2020, 7:59 a.m.

    Nếu a bằng b thì số cách tính thế nào nhỉ?


    • 1
      CNTT2_K59  commented on May 15, 2020, 4:19 p.m.

      Ui, em chưa xét trường hợp ý, chắc phải sửa lại đề thầy ạ.