A6281 | Welcome24ever 和方块

Welcome24ever 喜欢折叠和粘贴，今天他又开始玩方块了。

他有 $n$ 个立方体，从左到右排成一行，编号为 $1 \sim n$，每个立方体上写着一个正整数 $a_i$。另外，他还有 $k$ 张带有感叹号 '!' 的贴纸（可以把它当作“阶乘”操作），并且我们知道 $k \le n$。

对于某一个立方体，如果 Welcome24ever 在它上面贴上一张感叹号贴纸，那么这个立方体上的数字会立刻变成**这个数的阶乘**。例如：

- 如果某个立方体上写着 $5$，贴上感叹号后，它就会变成 $5! = 120$。

现在，Welcome24ever 想从这 $n$ 个立方体中选出若干个（也可以一个都不选），然后在被选中的立方体中，**最多选 $k$ 个**贴上感叹号。这样，每个被选中的立方体上最终会显示一个数（可能是原数，也可能是阶乘），所有被选中立方体上的最终数字之和要**恰好等于**给定的 $S$。

要求：

- 每个立方体**最多只能贴一张**感叹号贴纸；
- 如果两种方案中：
- 被选中的立方体集合相同，且
- 贴上感叹号的立方体集合也相同，

那么这两种方案视为**同一种方案**。

请你计算：一共有多少种不同的方案，使得所有被选中立方体上的最终数字之和恰好为 $S$。

第一行包含三个整数 $n, k, S$：

- $1 \le n \le 25$ —— 立方体的数量；
- $0 \le k \le n$ —— 感叹号贴纸的数量（最多可使用的阶乘操作次数）；
- $1 \le S \le 10^{16}$ —— 目标总和。

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$：

- $1 \le a_i \le 10^9$。

立方体按输入顺序从左到右视为 $1 \sim n$。
不同立方体上的数字可以相同。

输出一个整数，表示一共有多少种不同的方案，使得选出的立方体在进行“原数 / 阶乘”的最终处理后，它们的和恰好等于 $S$。