E. Аня и кубики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Аня очень любит складывать и наклеивать. Сегодня она решила заняться именно этим.

У Ани есть n кубиков, лежащих в ряд и пронумерованных от 1 до n слева направо, с написанными на них натуральными числами. Также у нее есть k наклеек с восклицательными знаками. Известно, что количество наклеек не превышает количества кубиков.

Аня может наклеить на кубик восклицательный знак и получить факториал числа, записанного на кубике. Например, если на кубике было написано 5, то после наклеивания будет 5!, что равно 120.

Вам нужно помочь Ане посчитать, сколько существует способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки, использовав не более k восклицательных знаков, так, чтобы сумма чисел, написанных на кубиках (как отмеченных восклицательными знаками, так и нет), после наклеивания стала равна S. Аня может наклеить на один кубик не более одного восклицательного знака. Справитесь?

Два способа будем считать одинаковыми, если совпадают номера оставленных кубиков, а также совпадают номера кубиков, на которые наклеены восклицательные знаки.

Входные данные

В первой строке входных данных заданы через пробел три целых числа n, k и S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1016) — количество кубиков и количество наклеек, которые есть у Ани, и сумма, которую необходимо набрать.

Во второй строке следуют n целых положительных чисел ai (1 ≤ ai ≤ 109) — числа, записанные на кубиках.

На разных кубиках могут быть написаны одинаковые числа.

Выходные данные

Выведите в первую строку выходных данных единственное целое неотрицательное число — количество способов оставить какое-то количество кубиков и наклеить на некоторые из них восклицательные знаки так, чтобы сумма чисел стала равна заданному числу S.

Примеры
Входные данные
2 2 30
4 3
Выходные данные
1
Входные данные
2 2 7
4 3
Выходные данные
1
Входные данные
3 1 1
1 1 1
Выходные данные
6
Примечание

В первом тесте из условия единственный способ достичь желаемого — оставить оба кубика, и наклеить на каждый из них по восклицательному знаку.

Во втором тесте из условия единственный способ достичь желаемого — оставить оба кубика, но не клеить восклицательный знак ни на один из них.

В третьем тесте из условия можно оставить любой из трёх кубиков, при этом на него можно как клеить, так и не клеить восклицательный знак, поэтому существует шесть способов достичь желаемого.