Задача Treats.  Василь Пупкін вирішив організувати олімпіаду по стрибкам в ширину. Він отримав n коробок з призами від спонсора. Кожна коробка  містить різні призи, але в кожній коробці призи однакові. З накладної відомо, що в i-й коробці міститься mi однакових призів. Василь вирішив нагородити  команду, що перемогла. Команда може отримати  не меньше a призів, та не більше ніж b призів. Тепер перед Василем постає  питання:   скільки дати  призів команді-переможцю та яких? Ваша задача підрахувати скількома способами він може розподілити призи.

Технічні умови. Програма Treats читає  в одному рядку  три цілих  числа: n, a та b, що розділені одним пропуском(1≤n≤10, 0≤a≤b≤10 000 000). Кожне з наступних n  цілих чисел такі, що  i+3 число - це mi – кількість цукерок в i-му пакунку. (0≤mi≤1000000). Програма виводить  на пристрій стандартного виведення k mod 109+7  (залишок від ділення кількості способів на 109+7 

Приклад

Введення

2 1 3 3 5

Виведення 

9

Коментар.  Призи можна розподілити такими способами:

(1,0),(2,0),(3,0),(0,1),(0,2),(0,3),(1,1),(1,2),(2,1)

© LIKT 1998-2018