Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P192PROE - Problem E - Bài toán những viên đá

Một ngày đẹp trời, Oppa đang trên đường đến tới trường thì gặp Unnie - crush bấy lâu nay. Sau một hồi lân la hỏi chuyện thì Oppa biết được crush của mình đang gặp rắc rối với một bài toán ở contest gần đây. Oppa muốn làm Unnie vui nhưng không biết phải làm sao nên đành nhờ các bạn.

Bài toán như sau:

Unnie có hai loại đá quý là đá thường và đá ma thuật. Với một viên đá ma thuật có thể tách thành m viên đá thường. Unnie có một khay chứa với n ô trống, mỗi viên đá sẽ chiếm 1 ô. Unnie ban đầu chọn 1 số viên đá ma thuật và bắt đầu tách một số trong số chúng. Một viên đá ma thuật nếu bị tách ra sẽ chiếm m ô. Ví dụ ban đầu có 3 viên đá ma thuật kí hiệu là 111, sau khi tách viên thứ 2 thành m viên thường(Kí hiệu là 0) với m = 2 thì sẽ được 1001. Hỏi có bao nhiêu trạng thái có thể của n ô trống.

Hai trạng thái là khác nhau nếu số lượng đá ma thuật ban đầu lấy khác nhau hoặc chỉ số các viên đá được tách ra khác nhau.

Input

Một dòng duy nhất chứa n và m. (1 ≤ n ≤ 1018, 2 ≤ m ≤ 20).

Output

In ra một dòng duy nhất là kết quả của bài toán khi chia lấy dư cho (109 + 7).

Example

Input
4 2

Output
5
Input
3 2

Output
3

Giải thích:

Có 5 trạng thái thỏa mãn là 1111, 0011, 1001, 1100, 0000.


Được gửi lên bởi:adm
Ngày:2019-02-23
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2020-02-18 14:35:42
test 15 là test ntn vậy ??
2019-03-12 02:29:12
Cứ bị sai sai ở test 15 ý! Ai chỉ dùm mik đc ko?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.