버섯 주인
시간 제한1초메모리 제한512 MB
0보다 큰 원소 x가 있으면 floor((x-1)/k)도 반드시 포함해야 한다는 조건을 만족하는, 크기 n인 음이 아닌 정수 집합의 개수를 1e9+7로 나눈 나머지로 구한다.
문제
말나르 씨는 올해 새해 파티를 열어 가장 친한 친구 n명을 초대하려고 한다. 일 년 중 가장 미친 밤인 만큼, 친구마다 버섯 하나를 선물할 것이다. 그 버섯으로 친구는 주문한 마르게리타 피자를 카프리치오사로 바꿀 수 있다.
말나르 씨는 버섯을 무한히 많이 가지고 있고, 각 버섯에는 서로 다른 음이 아닌 정수가 적혀 있다. 파티가 시작되기 전에 버섯을 자루에 넣고, 손님마다 자루에서 버섯 하나를 꺼낸다. 안타깝게도 모든 버섯이 들어갈 만큼 큰 자루를 구하지 못해서, 지금은 어떤 버섯을 자루에 넣을지 정할 수 없다. 잠시 더 고민한 끝에 다음과 같이 정했다.
- 파티가 시작되기 전 자루에는 정확히 n개의 버섯이 들어 있다.
- 자루에 x > 0이 적힌 버섯이 들어 있다면, ⌊(x−1)/k⌋가 적힌 버섯도 자루에 들어 있어야 한다.
말나르 씨를 도와 새해 파티를 위해 자루를 준비하는 서로 다른 방법의 수를 구하자.
참고: 방법의 수가 매우 클 수 있으므로 109 + 7로 나눈 나머지만 출력한다.
입력
첫째 줄에 자연수 n (2 ≤ n ≤ 1 000 000)과 k (1 ≤ k ≤ 1 000 000)가 주어진다.
출력
첫째 줄에 구하는 방법의 수를 109 + 7로 나눈 나머지를 출력한다.
힌트
첫 번째 예제 설명: 가능한 자루는 {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, {0, 2, 5}, {0, 2, 6}이다.