Đá Phép

Reziba có rất nhiều viên đá phép. Mỗi viên đá phép có thể được tách thành $M$ viên đá thường. Một viên đá (dù là đá phép hay đá thường) chiếm đúng $1$ đơn vị không gian, và một viên đá thường thì không thể tách tiếp.

Reziba muốn chọn một tập các viên đá phép rồi tách một số viên trong đó, sao cho tổng không gian bị chiếm bởi tập đá thu được đúng bằng $N$ đơn vị. Nếu một viên đá phép được chọn và được tách, nó chiếm $M$ đơn vị không gian (vì biến thành $M$ viên đá thường); nếu viên đá phép được chọn nhưng không tách, nó chiếm $1$ đơn vị.

Hỏi có bao nhiêu cấu hình khác nhau của tập đá thu được sao cho tổng không gian chiếm đúng $N$ đơn vị? In ra kết quả theo modulo ${10}^9+7$.

Hai cấu hình được xem là khác nhau nếu số viên đá phép mà Reziba lấy để tạo thành chúng khác nhau, hoặc vị trí (thứ tự) các viên đá bị tách khác nhau. Nói cách khác, một cấu hình là một dãy các viên đá xếp theo thứ tự, mỗi viên hoặc chiếm $1$ đơn vị (đá không tách) hoặc chiếm $M$ đơn vị (đá đã tách), với tổng độ dài bằng $N$.

Dữ liệu vào

Một dòng duy nhất gồm hai số nguyên $N$ và $M$.

Dữ liệu ra

In ra một số nguyên duy nhất — tổng số cấu hình, theo modulo ${10}^9+7$.

Ràng buộc

• $1\le N\le {10}^{18}$
• $2\le M\le 100$

Ví dụ