eolymp
bolt
Try our new interface for solving problems
Problems

Юрко та кубики

Юрко та кубики

Time limit 1.5 second
Memory limit 64 MiB

Юрко дуже любить складати і наклеювати. Сьогодні він вирішив зайнятися саме цим.У Юрка є n кубиків, що лежать в ряд і пронумерованих від 1 до n зліва направо, з написаними на них натуральними числами. Також у нього є k наклейок зі знаками оклику. Відомо, що кількість наклейок не перевищує кількості кубиків.Хлопчик може наклеїти на кубик знак оклику і отримати факторіал числа, записаного на кубику. Наприклад, якщо на кубику було написано 5, то після наклеювання буде 5!, що дорівнює 120.Вам потрібно допомогти Юрку порахувати, скільки існує способів залишити якусь кількість кубиків і наклеїти на деякі з них знаки оклику, використавши не більше k знаків оклику, так, щоб сума чисел, написаних на кубиках (як зазначених знаками оклику, так і ні) , після наклеювання стала дорівнює S. Юрко може наклеїти на один кубик не більше одного знаку оклику.

Два способи будемо вважати однаковими, якщо збігаються номери залишених кубиків, а також збігаються номери кубиків, на які наклеєні знаки оклику.

Input data

У першому рядку вхідних даних задано через пропуск три цілих числа n, k і S(1 ≤ n ≤ 25, 0 ≤ k≤ n, 1 ≤ S ≤ 10^16) - кількість кубиків і кількість наклейок, які є у Юрка, і сума, яку необхідно набрати.

У другому рядку йдуть n цілих позитивних чисел a[i](1 ≤ ai ≤ 10^9) - числа, записані на кубиках.На різних кубиках можуть бути написані однакові числа.

Output data

Виведіть в перший рядок вихідних даних єдине ціле невід'ємне число - кількість способівзалишити якусь кількість кубиків і наклеїти на деякі з них знаки оклику так, щоб сума чиселстала дорівнює заданому числу S.

Examples

Input example #1
2 2 30
4 3
Output example #1
1
Input example #2
3 1 1
1 1 1
Output example #2
6