CF525E.Anya and Cubes

Anya loves to fold and stick. Today she decided to do just that.

Anya has n cubes lying in a line and numbered from 1 to n from left to right, with natural numbers written on them. She also has k stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.

Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads 5, then after the sticking it reads 5!, which equals 120.

You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most k exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to S. Anya can stick at most one exclamation mark on each cube. Can you do it?

Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.

安雅喜欢折叠和粘贴。今天她决定就做这件事。

安雅有 $n$ 个立方体排成一行，从左到右编号为 $1$ 到 $n$，每个立方体上写有一个正整数。她还有 $k$ 张带感叹号的贴纸。已知贴纸的数量不超过立方体的数量。

安雅可以将一张感叹号贴纸贴在一个立方体上，从而将该立方体上的数字变为它的阶乘。例如，若一个立方体上写着 $5$，则贴上贴纸后它变为 $5!$，即 $120$。

你需要帮助安雅计算：有多少种方式可以选择若干个立方体，并在其中至多 $k$ 个被选中的立方体上贴上感叹号贴纸（每个立方体最多贴一张），使得这些被选中立方体在贴纸操作后的数字之和恰好等于 $S$？

如果两种方式所选择的立方体集合相同，且贴有感叹号的立方体集合也相同，则认为这两种方式是相同的。

The first line of the input contains three space-separated integers n, k and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1016) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get.

The second line contains n positive integers a__i (1 ≤ a__i ≤ 109) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one.

Multiple cubes can contain the same numbers.

输入的第一行包含三个用空格分隔的整数 $n$、$k$ 和 $S$（$1 \le n \le 25$，$0 \le k \le n$，$1 \le S \le 10^{16}$）——分别表示立方体的数量、Anya 拥有的贴纸数量，以及她需要达到的目标和。

第二行包含 $n$ 个正整数 $a_i$（$1 \le a_i \le 10^9$）——表示写在各个立方体上的数字。输入中给出的立方体按从左到右的顺序描述，起始为第一个立方体。

多个立方体上可以写有相同的数字。

Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number S.

输出选择若干个立方体并在其中一些上贴感叹号，使得这些数字之和等于给定数 $S$ 的方案数。

In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.

In the second sample the only way is to choose both cubes but don't stick an exclamation mark on any of them.

In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.

在第一个样例中，唯一的方法是选择两个立方体，并在每个立方体上贴一个感叹号。

在第二个样例中，唯一的方法是选择两个立方体，但不在其中任何一个上贴感叹号。

在第三个样例中，可以选择任意一个立方体，共有三种方式；并且对于所选的立方体，我们还可以选择贴或不贴感叹号。因此，总的方法数为六种。