Задачи
Подготовка соревнования
Подготовка соревнования
Однажды Арти попросили приготовить несколько соревнований по программированию. Так как он очень ленив, то решил немного сжульничать. Он приготовил n задач, для i-ой задачи он приготовил si
условий. Теперь он хочет составить соревнования из этих задач, удовлетворяющих следующим правилам:
- каждая задача в соревновании может быть использована только один раз;
- соревнование должно содержать от a до b задач;
- два соревнования считаются различными, если имеется задача которая присутствует в одном соревновании и отсутствует в другом, или если хотя бы одна задача имеет разные условия в этих соревнованиях;
- считаются множества задач, а не их порядок следования в соревнованиях.
Вычислить, сколько различных соревнований может подготовить Арти. Поскольку это значение может быть большим, то вывести его по модулю 109
+ 7.
Входные данные
Первая строка содержит числа n, a, b (1 ≤ a ≤ b ≤ n ≤ 10000). Вторая строка содержит n целых чисел si
(1 ≤ si
≤ 100).
Выходные данные
Вывести количество различных соревнований, которое может приготовить Арти, по модулю 109
+ 7.
Входные данные #1
2 1 2 3 4
Выходные данные #1
19