Yurko and the Blocks#8573
Yurko enjoys assembling and decorating things. Today, he decided to work with blocks. Yurko has blocks lined up in a row, numbered from to from left to right, each with a natural number written on it. In addition, he has stickers, each with an exclamation mark. It is known that the number of stickers does not exceed the number of blocks.
Yurko can place an exclamation mark on a block to replace the number written on it with its factorial. For example, if a block has the number , placing a sticker on it changes the number to 5! = 120.
Your task is to help Yurko count the number of ways to choose which blocks remain unchanged and which blocks receive an exclamation mark sticker, using at most stickers, such that the sum of the resulting numbers on all the blocks is exactly . Note that at most one exclamation mark sticker can be placed on any single block.
Two ways are considered the same if the sets of unchanged blocks and blocks with exclamation mark stickers are the same.
The first line contains three integers , , and (1 \leq n \leq 25,\ 0 \leq k \leq n,\ 1 \leq S \leq 10^{16}) — the number of blocks, the number of stickers, and the required total sum.
The second line contains positive integers a_1,\ a_2,\ \ldots,\ a_n (1 \leq a_i \leq 10^9) — the numbers written on the blocks. Different blocks may have the same number.
Print a single non-negative integer — the number of ways to leave some blocks unchanged and place exclamation mark stickers on some others so that the resulting sum of the numbers is equal to .
Example 1
Example 2