题目描述

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

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

Anya 可以在一个立方体上粘贴一个感叹号，使该立方体上的数字变为该数的阶乘。例如，如果某个立方体上的数字为 $5$，那么粘贴后它就变成 $5!$，即 $120$。

你需要帮助 Anya 计算，有多少种方式可以选择若干个立方体，并在其中至多 $k$ 个立方体上各贴一个感叹号，使得选择后这些立方体上显示数字的总和恰好为 $S$。每个立方体最多只能贴一个感叹号。

若两种方案选择的立方体集合相同，且贴感叹号的立方体集合也相同，则认为这两种方案是相同的。

输入格式

输入第一行包含三个用空格分隔的整数 $n$、$k$ 和 $S$，表示立方体的数量、Anya 拥有的贴纸数量，以及所需的总和。 $1\le n\le25,\ 0\le k\le n,\ 1\le S\le10^{16}$。

第二行包含 $n$ 个正整数 $a_{i}$，表示每个立方体上的数字。 $1\le a_{i}\le10^{9}$。

立方体在输入中按从左到右的顺序给出，从第一个立方体开始。

多个立方体上的数字可能相同。

输出格式

输出一个整数，表示有多少种方式可以选择若干立方体并在其中一些立方体上贴上感叹号，使这些立方体上的数字之和恰好等于指定的 $S$。

输入输出样例 #1

输入 #1

2 2 30
4 3

输出 #1

1

输入输出样例 #2

输入 #2

2 2 7
4 3

输出 #2

1

输入输出样例 #3

输入 #3

3 1 1
1 1 1

输出 #3

6

说明/提示

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

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

在第三个样例中，可以选择任意一个立方体，共有三种方式，并且可以选择是否贴上感叹号，因此总共有六种方式。

由 ChatGPT 5 翻译