Одинички (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