Загрузка [MathJax]/localization/ru/HTML-CSS.js

printРабочее место участника

printЗадачи

2753. Зельеделие

Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Профессор зельеделия Эзоп Шарп страдает от бессонницы и вынужден каждый день готовить себе сонное зелье. Сила зелья равна сумме сил добавленных в него ингредиентов и должна быть не меньше L (чтобы заснуть вечером), но и не больше U (чтобы вовремя проснуться утром). К счастью, в кладовой Хогвартса найдутся в изобилии ингредиенты с любой силой от 1 до 105, причем любые 2 разных вида ингредиентов имеют разную силу. Во избежание побочных эффектов от передозировки, один и тот же ингредиент нельзя добавлять в одно зелье более чем дважды. К сожалению, зелья вызывают привыкание: если выпить зелье с тем же составом ещё раз, оно не подействует. Сколько же дней профессор Шарп сможет справляться с бессоницей? Если число слишком большое, достаточно найти остаток от его деления на 109+9.

В единственной строке ввода содержатся два целых числа L и U (1LU105) – минимальная и максимальная сила зелья.

Вывести одно целое число – остаток от деления количества подходящих сонных зелий на 109+9.

Пример ввода

3 4

Пример вывода

6

Пояснение к примеру: Можно составить два зелья силы 3: из одного ингредиента силы 3, либо двух ингредиентов с силами 1 и 2. Также можно составить четыре зелья силы 4 из таких наборов ингредиентов: 4; 1+3; 1+1+2; 2+2. Зелья 1+1+1 и 1+1+1+1 использовать нельзя из-за передозировки ингредиента с силой 1.

loading