Юрко та кубики#8573
Юрко дуже любить збирати та прикрашати речі. Сьогодні він вирішив зайнятися цим з кубиками. У Юрка є кубиків, розташованих у ряд і пронумерованих зліва направо від до , на кожному з яких написане натуральне число. Також у нього є наклейок, кожна з яких містить знак оклику. Відомо, що кількість наклейок не перевищує кількість кубиків.
Юрко може наклеїти наклейку на кубик, щоб замінити число на ньому на його факторіал. Наприклад, якщо на кубику написано , після наклеювання воно стане 5! = 120.
Ваше завдання — допомогти Юрку порахувати, скількома способами можна вибрати, які кубики залишити без змін, а на які наклеїти наклейки (використовуючи не більше наклейок), щоб сума чисел на всіх кубиках дорівнювала . Зауважте, що на один кубик можна наклеїти не більше однієї наклейки.
Два способи вважаються однаковими, якщо множини незмінних кубиків і кубиків із наклейками збігаються.
У першому рядку містяться три цілі числа , та (1 \leq n \leq 25,\ 0 \leq k \leq n,\ 1 \leq S \leq 10^{16}) — кількість кубиків, кількість наклейок і потрібна сума.
У другому рядку містяться додатних чисел a_1,\ a_2,\ \ldots,\ a_n (1 \leq a_i \leq 10^9) — числа на кубиках. На різних кубиках можуть бути однакові числа.
Виведіть одне невід'ємне число — кількість способів залишити деякі кубики без змін, а на інші наклеїти наклейки так, щоб сума чисел дорівнювала .
Приклад 1
Приклад 2