Migrated from Lutece 2992 How Many Basketballs!

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

在篮球课上，小蓝正在考虑一个困难的问题：$2^k$ 与 $k!$ 的值哪一个更大。（其中 $!$ 表示阶乘符号）

小荞作为小蓝的篮球老师，一眼就看出了答案，望着正在数篮球的小蓝摇了摇头。此时一个新的想法在小荞的脑袋中蹦出：篮球场共有 $n$ 个球，由于 $n$ 非常小表示，我们在每个篮球上给出一个数字 $a_i$，同时选择 $n$ 位同学，同学的编号从 $1$ 到 $n$，每位同学随机抽一个篮球，然后按照同学编号从小到大的顺序，每位同学可以根据自己的选择，执行以下四个操作之一：

1. 扔掉这个球，什么都不做；
2. 直接报出这个球上的数字 $a_i$
3. 计算出 $2^{a_i}$，并报出这个数字；
4. 计算出 $a_i!$ ，并报出这个数字。

值得注意的是，小荞规定了操作③和操作④的总数不能超过 $m$。当后面的同学发现前面的同学使用的操作③④数量总和等于 $m$ 时，他们不得不只能使用操作①②。

最后小蓝会把所有听到的数字加起来，得到所有数的和为 $sum$。

从每位同学拿到自己的球后，小荞心中就对 $sum$ 有了一个估计量 $S$，他把这个值告诉了你，请你计算小荞猜测准确的概率，即求 $P(sum = S)$。

注意，每个同学拿到自己的球后，两种方案被视为不同，当且仅当两种方案中至少有一个同学的选择操作不一样。

Input

第一行三个整数 $n,m,S$ ，表示篮球的个数，操作的限制数，小荞的对答案的估计量。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示篮球上面的数字。

Output

输出一行一个整数，表示答案在模 $998244853$ 意义下的值。

Samples

6 2 1
1 1 4 5 1 4

58136419

7 3 9
1 9 1 9 8 1 0

669477200

Constraints

$1\leq m\leq n\leq 24, \ 0\leq S \leq 10^{18}, \ 0\leq a_i\leq 10^{18}$

Note

对于样例 $1$ ，执行了操作②③④的同学拿到的篮球上的数字只可能是 $1$，拿到这些球的人又显然只有一个人能执行操作②或④，因此有 $3 \times 2 = 6$ 种可能性。一共有 $2^6\times (1 + 6 + 15)=1408$ 次种可能的取值，因而答案为 $\frac{6}{1408} = \frac{3}{704}$ ，在模 $998244853$ 的意义下，答案为 $58136419$ 。

对于样例 $2$，共有 $18$ 种可能性。

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming