Задача O. Человек с рассеченной судьбой ≡

Условие

Мистеру Невиллу Сент-Клеру 37 лет. Живет он скромно, хороший муж и любящий отец, люди, встречающиеся с ним, отзываются о нем превосходно. Определенных занятий у него нет, но он принимает участие в нескольких коммерческих предприятиях. Обосновался на собственной вилле "Кедры" в Кенте.

Угрюмый калека Хью Бун — профессиональный нищий, для вида продающий восковые спички. У него оранжево-рыжие волосы, бледное лицо, изуродованное чудовищным шрамом, и отменное чувство юмора, выделяющее его из толпы попрошаек. Дождь милостыни так и льется в грязную кожаную кепку, которая лежит перед ним на мостовой, в нише на левой стороне лондонской Трэд-Нидл-стрит.

Преображение в нищего приносит Невиллу постоянный хороший доход. Конечно, есть дни, когда он вынужден оставаться дома (например, семейные праздники), но обычно он составляет расписание на ближайшие дни, чтобы его сообщник-ласкар, знал, когда ждать своего особого жильца.

Помогите мистеру Невиллу определить количество подходящих расписаний на ближайшие n дней, из которых ровно k дней он посвятит "работе". Чтобы не вызвать подозрений у полиции, Хью Бун никогда не просит милостыню два дня подряд. Также известны дни, когда Сент-Клер должен будет остаться дома.

Формат входных данных

Первая строка входного файла содержит натуральное число n — общее количество дней. Вторая строка содержит натуральное число k — количество дней, в течение которых Невилл собирался просить милостыню. Третья строка входного файла содержит натуральное число p — количество дней, которые ему нужно провести с семьей. В четвертой строке через пробел в порядке возрастания расположены натуральные числа d_i — номера таких дней.

Формат выходных данных

Выведите одно неотрицательное целое число — количество подходящих расписаний.

Ограничения

1 ≤ n ≤ 100

1 ≤ k, p, d_i ≤ n

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере из пяти дней Невилл два дня хочет посвятить сбору милостыни. К сожалению (или к счастью?) в первый, второй и пятый день он должен быть с семьей, а "работать" два дня подряд (в третий и четвертый) он не может. Подходящих расписаний нет.

Во втором примере Невилл сможет "работать" два дня из пяти (в третий и пятый дни). Расписание единственное.

В третьем примере Невилл должен быть с семьей только в четвертый день. Есть четыре подходящих расписания:

Невилл "работает" в первый и третий дни;

Невилл "работает" в первый и пятый дни;

Невилл "работает" во второй и пятый дни;

Невилл "работает" в третий и пятый дни.

Примеры тестов

5
2
3
1 2 5

0

5
2
3
1 2 4

1

5
2
1
4

4