Зельеделие
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Профессор зельеделия Эзоп Шарп страдает от бессонницы и вынужден каждый день готовить себе сонное зелье.
Сила зелья равна сумме сил добавленных в него ингредиентов и должна быть не меньше `L` (чтобы заснуть вечером), но и не
больше `U` (чтобы вовремя проснуться утром).
К счастью, в кладовой Хогвартса найдутся в изобилии ингредиенты с любой силой от 1 до `10^5`, причем любые 2 разных вида ингредиентов
имеют разную силу.
Во избежание побочных эффектов от передозировки, один и тот же ингредиент нельзя добавлять в одно зелье более чем дважды.
К сожалению, зелья вызывают привыкание: если выпить зелье с тем же составом ещё раз, оно не подействует.
Сколько же дней профессор Шарп сможет справляться с бессоницей?
Если число слишком большое, достаточно найти остаток от его деления на `10^9+9`.
В единственной строке ввода содержатся два целых числа `L` и `U` (`1 <= L <= U <= 10^5`) -- минимальная и максимальная сила зелья.
Вывести одно целое число -- остаток от деления количества подходящих сонных зелий на `10^9+9`.
```sample Пример ввода
3 4
```
```sample Пример вывода
6
```
Пояснение к примеру: Можно составить два зелья силы 3: из одного ингредиента силы 3, либо двух ингредиентов с силами 1 и 2.
Также можно составить четыре зелья силы 4 из таких наборов ингредиентов: 4; 1+3; 1+1+2; 2+2.
Зелья 1+1+1 и 1+1+1+1 использовать нельзя из-за передозировки ингредиента с силой 1.
Начало
Соревнования
Динамическое программирование и запоминающие функции