Однажды Арти попросили подготовить несколько соревнований по программированию. Поскольку он очень ленив, то он решил немного схитрить. Арти подготовил задач, а для -й задачи подготовил условий. Теперь он хочет собрать конкурсы из этих заданий по следующим правилам:
каждую задачу можно использовать в соревновании только один раз;
соревнование должно содержать от до задач;
два соревнования считаются разными, если имеется хотя бы одна задача, которая присутствует в одном соревновании, а не во втором, или если имеется хотя бы одна задача с разными формулировками в этих соревнованиях;
важен только набор задач, а не их порядок.
Подсчитайте, сколько разных соревнований может подготовить Арти. Так как это число может быть очень большим, выведите его по модулю .
Первая строка содержит , , ).
Вторая строка содержит целых чисел ().
Выведите одну строку — количество различных соревнований, которые Арти может подготовить по модулю .