Юрко и кубики
Юрко обожает складывать и наклеивать. Сегодня он решил заняться именно этим. У Юрка есть n кубиков, выстроенных в ряд и пронумерованных от 1 до n слева направо, на которых написаны натуральные числа. Также у него есть k наклеек со знаками восклицания. Известно, что количество наклеек не превышает количество кубиков. Юрко может наклеить знак восклицания на кубик, чтобы получить факториал числа, написанного на этом кубике. Например, если на кубике написано 5, то после наклеивания получится 5!, что равно 120. Ваша задача — помочь Юрку определить, сколько существует способов оставить некоторое количество кубиков и наклеить на некоторые из них знаки восклицания, использовав не более k наклеек, так, чтобы сумма чисел на кубиках (как отмеченных знаками восклицания, так и нет) стала равна S. На один кубик можно наклеить не более одного знака восклицания.
Входные данные
В первой строке входных данных заданы через пробел три целых числа n, k и S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10^16) — количество кубиков, количество наклеек у Юрка и требуемая сумма.
Во второй строке указаны n целых положительных чисел a[i] (1 ≤ a[i] ≤ 10^9) — числа, написанные на кубиках. На разных кубиках могут быть одинаковые числа.
Выходные данные
Выведите одно целое неотрицательное число — количество способов оставить некоторое количество кубиков и наклеить на некоторые из них знаки восклицания так, чтобы сумма чисел стала равна заданному числу S.