Bedao Regular Contest 06 - HALLOWEEN

View as PDF

Submit solution


Points: 0.40 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vào lễ Halloween hàng năm, các đứa trẻ thường ghé thăm những ngôi nhà để được phát kẹo. Copium là một người rất hào phóng nên đã chuẩn bị tươm tất các loại kẹo ở nhà để phát cho những đứa trẻ gõ cửa nhà mình. Ban đầu có sẵn ~n~ viên kẹo được chia vào ~m~ túi quà, nhưng để đảm bảo đứa trẻ nào cũng có phần nên Copium muốn mọi túi quà đều có đúng ~k~ viên kẹo. Vì vậy, mỗi lần anh ấy sẽ chọn ra ~1~ túi quà rồi thêm hoặc bớt tùy ý ~1~ viên kẹo từ túi quà đó (hiển nhiên là số kẹo không được âm).

Đếm số cách chia ~n~ viên kẹo vào các túi quà ban đầu sao cho:

  • Số túi quà ~m~ là tối đa ~(~vài túi quà có thể không chứa kẹo nên số kẹo mỗi túi phải lớn hơn hoặc bằng ~0~~)~.
  • Số lần thêm bớt tối thiểu để mọi túi quà đều có ~k~ viên kẹo là số lần thêm bớt tối thiểu để các túi quà có cùng lượng kẹo.
  • Với mọi cặp số ~i, j~ ~( 1 \leq i, j \leq m )~, nếu túi quà thứ ~i~ có ít hơn ~k~ viên kẹo và túi quà thứ ~j~ có từ ~k~ viên kẹo trở lên thì ~i < j~.

Input

  • Một dòng gồm ~2~ số nguyên lần lượt là ~n~ và ~k~, là số viên kẹo và số viên kẹo Copium muốn có trong mỗi túi quà ~( 1 \leq n, k \leq 10^{14} )~.

Output

  • Số cách chia thỏa mãn yêu cầu đề bài, do đáp án có thể rất lớn nên in ra phần chia dư cho ~10^9+7~.

Sample Input

5 2

Sample Output

4

Note

Có ~4~ cách chia kẹo thỏa mãn, với số túi quà tối đa là ~m = 4~:

  • ~[0, 1, 2, 2]~
  • ~[1, 0, 2, 2]~
  • ~[0, 0, 3, 2]~
  • ~[0, 0, 2, 3]~

Subtask

  • ~40\%~ số test có ~1 \leq n, k \leq 2 \times 10^6~.
  • ~60\%~ số test còn lại không có điều kiện gì thêm.

Comments

Please read the guidelines before commenting.