Migrated from Lutece 2660 我心爱的小企鹅

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

星宮汐最喜欢企鹅啦！

汐宝把自己的 $n$ 只企鹅排成一行，从左到右从 $1$ 到 $n$ 编号，每只切身上都有一个数。 她还有 $k$ 个带有感叹号的贴纸，并且知道贴纸的数量不超过企鹅的数量。

我们可以在企鹅上贴一个感叹号，让它身上的数变成它的阶乘。 例如，如果一只企鹅身上的数是 $5$，那贴上感叹号后它身上的数就变成了 $120$，因为 $5!=120$。

于是汐宝可以通过选一些企鹅，并在最多 $k$ 只企鹅的贴上感叹号，使得这些企鹅身上的数之和等于 $S$。 注意每只企鹅身上只能贴一个感叹号！汐宝想知道到底有多少种选贴方案可以满足上述操作要求呢？

※如果两种选贴方案选了相同的企鹅且贴了相同的企鹅，则认为它们是相同的。

Input

输入的第一行包含三个空格分隔的整数 $n,k$ 和 $S$ ，其中 $1 \le n \le 25, 0 \le k \le n, 1 \le S \le 10^{16}$ 。

它们分别代表汐宝拥有的企鹅总数、感叹号贴纸总数和她想得到的编号和 。

第二行包含 $n$ 个正整数 $a_i\ (1 \le a_i \le 10^9)$， $a_i$ 表示第 $i$ 只企鹅身上的初始数字。

不同的企鹅可能身上有着相同的初始数字。

Output

输出使所选企鹅身上数字之和等于给定的数字 $S$ 的选贴方案总数。

Samples

2 2 30
4 3

1

2 2 7
4 3

1

3 1 1
1 1 1

6

Note

样例 1 解释：唯一的选贴方案是选择两只企鹅并在每只企鹅身上贴感叹号。 样例 2 解释：唯一的选贴方案是选择两只企鹅，但不在任一只企鹅身上贴感叹号。

Resources

2021 UESTC ICPC Training for String and Search Algorithm