题目描述

你有$n$个数$a_i$，以及$k$个$!$，每个$!$可以使一个数$a_i$变成$a_i!$（同一个数至多变一次）。

其中，$a_i!$表示$a_i$的阶乘，如$4!=1\times 2\times 3\times 4=24$。

现在，你可以选出任意个数，并使用不超过$k$个$!$，问使这些数的和等于$S$的方案数。

输入格式

第一行输入三个整数$n,k,S$。 第二行输入$n$个整数$a_i$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

3 1 1
1 1 1

样例输出 #1

6

说明/提示

有$1\leq k\leq n\leq 25,0\leq a_i\leq 10^9,1\leq S\leq 10^{16}$。