리그 오브 레전설 (Large)
시간 제한3초메모리 제한256 MB
1초짜리 스킬 A와 M초짜리 스킬 B로 N초를 쉬는 시간 없이 정확히 채우는 조합의 수를 1,000,000,007로 나눈 나머지를 구한다.
문제
규환이는 리그 오브 레전설이라는 게임을 좋아한다. 이 게임에서는 N초 동안 싸움을 하는데, 규환이가 플레이하는 캐릭터는 A, B 두 가지 스킬을 사용할 수 있다. A 스킬의 시전 시간은 1초이고, B 스킬의 시전 시간은 M초이다. 규환이는 다양한 스킬 조합을 원하기 때문에 가능한 모든 스킬 조합을 알아보고 싶어 한다. 단, 시전 시간 동안은 다른 스킬을 사용할 수 없으며, 스킬을 안 쓰고 있는 시간은 없어야 한다.
예를 들어 N이 4초이고 M이 2초이면 가능한 스킬 조합은 AAAA, AAB, ABA, BAA, BB로 5가지다.
입력
첫 번째 줄에 싸움 시간 N과 B 스킬의 시전 시간 M이 주어진다. (N은 1018 이하의 자연수, M은 2 이상 100 이하의 자연수)
출력
가능한 조합의 수를 1,000,000,007로 나눈 나머지를 출력한다.