Задача Trunks. Скрудж Макдак знайшов печеру, де в один ряд стояли скрині. На стіні печери написано:
- З першої скрині можна взяти рівно K монет;
- З кожноі наступної скрині можна взяти довільну кількість монет, але хоча б одну;
- Не можна брати з наступної скрині стільки ж монет, що і з попередньої;
- Якщо з чергової (останньої на цей час) скрині взяти менше монет, ніж з передостанньої, то з наступної треба взяти більше, ніж з останньої;
- Якщо з останньої скрині взяти більше монет, ніж з передостанньої, то з наступної треба взяти менше, ніж з останньої;
- Загалом можна взяти рівно N монет.
Допоможіть Скруджу підрахувати, скількома способами він зможе винести з печери монети. Вважайте, що скринь, а також монет у кожній скрині достатньо.
Технічні умови. Програма Trunks читає з пристрою стандартного введення числа N і K (1≤N≤5000, 1≤K≤N) і виводить на пристрій стандартного виведення остачу при ділення шуканої кількості на 109+7.
Приклади
Введення 3 3
Виведення 1
Введення 6 2
Виведення 4
Пояснення. Для другого прикладу можливі способи: [2,1,2,1], [2,1,3], [2,3,1], [2,4].