D. Магические камни
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Reziba есть много магических камней. Каждый магический камень может быть разделен на $$$M$$$ обычных камней. Каждый магический (и обычный) камень занимает $$$1$$$ единицу пространства. Обычный камень не может быть разделен.

Reziba хочет выбрать набор магических камней и разделить некоторые из них таким образом, чтобы общее пространство, занятое получившимся множеством, было равно $$$N$$$. Если магический камень выбран и разделен, он занимает $$$M$$$ единиц пространства (потому что это разделение на $$$M$$$ камней); если же магический камень не разделен, то он занимает $$$1$$$ единицу пространства.

Как много различных конфигураций получившихся множеств камней может иметь Reziba, если общее пространство, занятое этим множеством, равно $$$N$$$? Выведите ответ по модулю $$$1000000007$$$ ($$$10^9+7$$$). Две конфигурации считаются различными, если количество магических камней, которые имеет Reziba, различается, или индексы камней, которые Reziba не разделяет, различаются.

Входные данные

Выходные данные содержат единственную строку, содержащую $$$2$$$ целых числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 10^{18}$$$, $$$2 \le M \le 100$$$).

Выходные данные

Выведите одно целое число — количество конфигураций результирующих наборов камней таких, что общее занимаемое ими пространство равно $$$N$$$. Выведите ответ по модулю $$$1000000007$$$ ($$$10^9+7$$$).

Примеры
Входные данные
4 2
Выходные данные
5
Входные данные
3 2
Выходные данные
3
Примечание

В первом тестовом примере каждый магический камень может быть разделен на $$$2$$$ обычных камня, и мы знаем, что общее количество камней равно $$$4$$$.

Пусть $$$1$$$ обозначает магический камень, а $$$0$$$ обозначает обычный камень.

Все конфигурации, которые вы можете иметь:

  • $$$1 1 1 1$$$ (никакие камни не разделены);
  • $$$0 0 1 1$$$ (первый магический камень разделен на $$$2$$$ обычных камня);
  • $$$1 0 0 1$$$ (второй магический камень разделен на $$$2$$$ обычных камня);
  • $$$1 1 0 0$$$ (третий магический камень разделен на $$$2$$$ обычных камня);
  • $$$0 0 0 0$$$ (первый и второй магические камни разделены суммарно на $$$4$$$ обычных камня).

Таким образом, ответ равен $$$5$$$.