Подарок
Карев обожает простые последовательности длиной не более K чисел. Простая последовательность длины K — это последовательность, состоящая из чисел от 0 до K-1 в указанном порядке. Например, простыми последовательностями являются {0}, {0,1,2,3}, {0,1,2,3,4,5,6}, тогда как {1}, {0,1,3,2}, {0,1,3} — не являются простыми.
В преддверии дня рождения Карева, Полли хочет подарить ему несколько простых последовательностей, объединив их в интересную последовательность. Интересная последовательность создается путем конкатенации нескольких простых последовательностей, каждая из которых имеет длину не более K. Например, если K = 3, то {0,1,2,0}, {0,1,0,1}, {0,0,0} и {0,1,2} являются интересными последовательностями, но {0,1,2,3}, {0,1,1} и {0,0,2} — не являются.
Полли может выбрать множество последовательностей и теперь интересуется, сколько у нее действительно есть вариантов. Карев — её близкий друг, и она хочет сделать ему действительно значимый подарок.
Напишите программу, чтобы помочь Полли решить следующую задачу: даны K — максимальная длина простых последовательностей, которые Полли может приобрести, и N — длина интересной последовательности, которую она хочет создать. Вычислите, сколько различных интересных последовательностей она может составить. Поскольку это число может быть очень большим, выведите его по модулю 10^9+7.
Входные данные
На первой строке стандартного ввода даны два числа, разделенные пробелом — N и K(1 ≤ K ≤ N ≤ 2000000 ).
Выходные данные
Вы должны вывести одно число на первой строке стандартного вывода — количество различных интересных последовательностей, которые Полли может составить с текущими ограничениями. Выведите ответ по модулю 10^9+7.
Объяснение для первого примера
Пусть K=3 и N=4. Возможные интересные последовательности:{0,0,0,0}; {0,0,0,1}; {0,0,1,0}; {0,0,1,2}; {0,1,0,0}; {0,1,0,1}; {0,1,2,0}. Таким образом, существует 7 последовательностей, и это ответ для этого примера.