Единицы (Onestransform)
В то время, когда Вася работал над конструкцией из зеркал, Коле было очень тоскливо. Он сидел и неторопливо рисовал на листочке через запятую последовательность единиц. В конце концов ему удалось написать достаточно длинную последовательность из N единичек и тут… Эврика! Николаю пришло в голову, что с этой последовательностью можно сделать некоторые преобразования. Он решил заменять произвольное количество последовательных единиц числом, которое равняется количеству замененных единиц. Очевидно, что таких замен можно сделать очень много и, чтобы уменьшить количество возможных преобразований, Коля решил поставить ограничение на количество заменяемых единиц, не превышающее число k.
Так например, когда последовательность содержит пять единиц, а k=2, самой длинной замененной последовательностью может быть последовательность, которая содержит не более двух единиц, т.е. 1,1,1,1,1можно заменить на 2 1 1 1 либо 2 2 1, либо 1 2 2 либо 2 1 2, но нельзя на 4 1 или 3 2.
Обратите внимание, что единицы можно заменить только из начального набора. Единицы, которые есть в составе числа, полученного после преобразования, например, 11, 211 или 111, замене не подлежат.
Технические условия
Программа Onestransform читает со стандартного устройства ввода (клавиатуры) два натуральных числа N (1 ≤ N ≤ 107) – количество единиц в последовательности и k (1 ≤ k ≤ 107) – число, которое указывает на максимально возможное количество единиц, которые подлежат замене (позволяется заменять не более k единиц).
Программа выводит на стандартное устройство вывода (экран) единственное число – количество возможных преобразований по модулю 109 + 7.
Пример
| Ввод | Вывод |
| 4 3 | 7 |
Пояснения к тесту:
Для N=4 последовательность имеет вид: 1,1,1,1. Возможные преобразования следующие:
1 1 1 1
1 1 2
1 2 1
2 1 1
3 1
1 3
2 2