A91483.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$。

样例解释 #1

唯一的方案是：

• 选中两个立方体；
• 在两个立方体上都贴上感叹号：

$$4! + 3! = 24 + 6 = 30.$$

样例解释 #2

唯一的方案是：

• 选中两个立方体；
• 都不贴感叹号：

$$4 + 3 = 7.$$

样例解释 #3

共有三块写着 1 的立方体：

• 可以选择其中任意一个（3 种选法），
• 对于每个被选中的立方体，又可以选择“贴”或“不贴”感叹号（但不论是否贴，值都是 1），

因此共有 $3 \times 2 = 6$ 种不同的方案。