Радіоактивні банани#168

Радіоактивні банани

1 секунда
512 мегабайтів
Середня

У коров'ячому селі кожна корова володіє рівно одним будинком. Ці будинки розташовані по прямій лінії. будинків позначено від до в порядку їх віддалення від центру села, починаючи з будинку, найближчого до центру села.

Бананів у Леді багато – вистачить усім коровам, і сьогодні вона дуже щедра! Вона вирішила роздати коровам частину своїх бананів.

Однак, як ми всі знаємо, банани є радіоактивними. Що ще гірше, банани Леді особливо радіоактивні, тому що вона живе поруч з екватором, де середній потік космічних променів найвищий. Якщо надто багато бананів Леді розміщувати в безпосередній близькості один від одного, вони можуть викликати ядерний вибух, який, безсумнівно, призведе до погіршення іміджу Леді. Леді зберігає свої банани в маленьких коробочках, але їй доведеться відкрити їх, якщо вона хоче віддати їх коровам. Щоб запобігти ядерному вибуху, Леді повинна розподілити свої банани відповідно до таких правил:

Так, наприклад, якщо N = 4 і C = 2, Леді може дати банан кожної корові у будинках , і , але вона не може дати по банану усім коровам в будинках , і , тому що будинки , та розташовані поруч один з одним, і виникне ядерний вибух.

Леді хоче знайти кількість способів розподілити свої банани між коровами, по модулю 1\,000\,000\,007. Зверніть увагу, що немає обмежень на кількість бананів, які Леді може роздавати коровам – зокрема, Леді може не дати коровам взагалі бананів.

Вхідні дані

Єдиний рядок вхідного файлу містить два додатних числа: – кількість будинків і – кількість послідовних будинків, які можуть отримати банани, не викликаючи ядерного вибуху.

Вихідні дані

У вихідний файл виведіть одне число – кількість способів, якими Леді може розподілити свої банани між коровами по модулю 1\,000\,000\,007.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Приклад 3

Loading
Loading

Примітка

Для першого прикладу (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