Yurko and the Blocks
Yurko enjoys assembling and decorating objects. Today, he has decided to work with blocks. Yurko has n blocks lined up in a row, numbered from 1 to n from left to right, each with a natural number written on it. Additionally, he has k stickers, each featuring an exclamation mark. It's known that the number of stickers does not exceed the number of blocks. Yurko can place an exclamation mark on a block to transform the number on it into its factorial. For instance, if a block displays the number 5, placing a sticker on it would change it to 5!, which equals 120. Your task is to help Yurko determine how many different ways he can choose to leave some blocks unchanged and place exclamation marks on others, using no more than k stickers, so that the total sum of the numbers on the blocks (both with and without exclamation marks) equals S. Note that Yurko can place at most one exclamation mark on any single block.
Two configurations are considered identical if the numbers on the unchanged blocks and the numbers on the blocks with exclamation marks are the same.
Input
The first line of the input contains three integers n, k, and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10^{16}) - representing the number of blocks, the number of stickers Yurko has, and the target sum to achieve.
The second line contains n positive integers a[i] (1 ≤ a[i] ≤ 10^9) - the numbers written on the blocks. Note that different blocks may have the same numbers.
Output
Output a single non-negative integer on the first line, representing the number of ways to leave some blocks unchanged and place exclamation marks on others so that the sum of the numbers equals the specified number S.