安雅喜欢折叠和粘贴。今天她决定这么做。
Anya 有 n 个立方体排成一行,从左到右编号为 1 到 n,上面写有自然数。她还有带有感叹号的 k 贴纸。我们知道贴纸的数量不会超过立方体的数量。
Anya可以在立方体上贴一个感叹号,并得到立方体上写的数字的阶乘。例如,如果一个立方体读数为 5,则粘贴后读数为 5!,等于 120。
你需要帮助 Anya 数出有多少种选择某些立方体的方式,并在选定的某些立方体上最多粘贴 k 个感叹号,使得粘贴后所选立方体上写的数字之和等于 S。 Anya 最多可以在每个立方体上粘贴 1 个感叹号。你能做到吗?
如果两种方法具有相同的选定立方体集和相同的带有感叹号的立方体集,则认为它们是相同的。
输入
输入的第一行包含三个空格分隔的整数 n、k 和 S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 1016)——Anya 拥有的立方体数量和贴纸数量,以及她需要获得的总和。
第二行包含 n 个正整数 ai (1 ≤ ai ≤ 109) — 写在立方体上的数字。输入中的立方体按从左到右的顺序描述,从第一个立方体开始。
多个立方体可以包含相同的数字。
输出
输出选择一些立方体的方法数,并在其中一些立方体上贴上感叹号,使数字之和等于给定的数字S。
示例
输入 #1
2 2 30 4 3
输出 #1
1
输入 #2
2 2 7 4 3
输出 #2
1
输入 #3
3 1 1 1 1 1
输出 #3
6
注意
在第一个示例中,唯一的方法是选择两个立方体并在每个立方体上贴上感叹号。
在第二个示例中,唯一的方法是选择两个立方体,但不要在其中任何一个上粘贴感叹号。
在第三个示例中,可以通过三种方式选择任何立方体,并且我们也可以选择在其上粘贴或不粘贴感叹号。所以,总共有六种方式。