Юрко дуже любить складати і наклеювати. Сьогодні він вирішив зайнятися саме цим. У Юрка є 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.