У коров'ячому селі кожна корова володіє рівно одним будинком. Ці будинки розташовані по прямій лінії. будинків позначено від до в порядку їх віддалення від центру села, починаючи з будинку, найближчого до центру села.
Бананів у Леді багато – вистачить усім коровам, і сьогодні вона дуже щедра! Вона вирішила роздати коровам частину своїх бананів.
Однак, як ми всі знаємо, банани є радіоактивними. Що ще гірше, банани Леді особливо радіоактивні, тому що вона живе поруч з екватором, де середній потік космічних променів найвищий. Якщо надто багато бананів Леді розміщувати в безпосередній близькості один від одного, вони можуть викликати ядерний вибух, який, безсумнівно, призведе до погіршення іміджу Леді. Леді зберігає свої банани в маленьких коробочках, але їй доведеться відкрити їх, якщо вона хоче віддати їх коровам. Щоб запобігти ядерному вибуху, Леді повинна розподілити свої банани відповідно до таких правил:
Корова отримує не більше одного банану.
Не більше, ніж корів, що мають послідовні номери будинків, всі можуть отримати банани.
Так, наприклад, якщо N = 4 і C = 2, Леді може дати банан кожної корові у будинках , і , але вона не може дати по банану усім коровам в будинках , і , тому що будинки , та розташовані поруч один з одним, і виникне ядерний вибух.
Леді хоче знайти кількість способів розподілити свої банани між коровами, по модулю 1\,000\,000\,007. Зверніть увагу, що немає обмежень на кількість бананів, які Леді може роздавати коровам – зокрема, Леді може не дати коровам взагалі бананів.
Єдиний рядок вхідного файлу містить два додатних числа: – кількість будинків і – кількість послідовних будинків, які можуть отримати банани, не викликаючи ядерного вибуху.
У вихідний файл виведіть одне число – кількість способів, якими Леді може розподілити свої банани між коровами по модулю 1\,000\,000\,007.
Example 1
Example 2
Example 3
Для першого прикладу (N=4, C=2) існує наборів номерів будинків, які задовольняють наведеним вище правилам: \{1,2,4\}, \{1,3,4\}, , , , , , , , , , , .
Для другого прикладу (N=3, C=1) існує наборів номерів будинку, які задовольняють наведеним вище правилам: , , , , . Зверніть увагу, що дозволено, оскільки будинки та не розташовані поруч один з одним, тому ядерного вибуху не відбудеться.
Для третього прикладу (N=3, C=5) Леді не потрібно турбуватися про друге правило, оскільки немає п'яти номерів послідовних будинків. Таким чином, усі підмножин задовольняють наведеним в умові правилам: \{1,2,3\}, , , , , , , .
Ця задача складається з восьми підзадач. Для підзадач виконуються додаткові обмеження, вказані в таблиці. Бали за підзадачу будуть нараховані лише за умови проходження усіх тестів підзадачі.
№ підзадачі | Бали | Обмеження | Примітка |
0 | 0 | Тести з умови | |
1 | 9 | 0 < N < C < 200 | |
2 | 2 | 0 \le N \le 10^6; C = 1 | |
3 | 5 | 0 < N < 16; 0 < C < 16 | |
4 | 7 | 0 < N < 10^5; 0 < C < 20 | |
5 | 19 | 0 < N < 10^6; 0 < C < 200 | |
6 | 12 | 0 < N < 10^{18}; C = 1 | |
7 | 13 | 0 < N < 10^{18}; 0 < C < 50 | |
8 | 33 | 0 < N < 10^{18}; 0 < C < 200 |