题目描述

你在做一道数学题。

你觉得最终的答案可以由 $a_1 \times a_2 \times \cdots \times a_n$ 得到，便算出了这个乘积。

但是你发现，正确答案是 $m$。

你觉得答案的形式应该是正确的，问题可能出在其中几项 $a_i$ 算错了。

正确的分解应该具有 $m = b_1\times b_2 \times \cdots \times b_n$ 的形式，其中至少有 $1$ 个 $b_i$ 与 $a_i$ 不同；同时，你希望你没有算错很多项 $a_i$，也即最多有 $l$ 个 $b_i$ 与 $a_i$ 不同。

你想知道有多少种满足要求的有序序列 $b_1, b_2, \cdots, b_n$。如果恰好只有一种正确的分解，那就不需要从头检查了。

输入格式

输入的第一行包含三个正整数 $n, m, l$，分别表示乘积的项数，正确的乘积，以及最多可能算错的项数。保证 $1\le l\le n\le 100$，$1\le m \le 10^{11}$。

输入的第二行包含 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，表示原来的各项。保证 $1\le a_i \le m$。

输出格式

输出一个非负整数，表示可能的分解种数对 $998,244,353$ 取模的结果。

样例数据

样例 1 输入

3 18 1
3 3 3

样例 1 输出

3

可能的分解为 $2\times 3\times 3$，$3\times 2\times 3$ 和 $3\times 3\times 2$。

样例 2 输入

3 20240414 2
24 4 14

样例 2 输出

0

$20240414 = 2\times 23\times 440009$，故不存在满足要求的分解。

样例 3 输入

3 20240414 3
24 4 14

样例 3 输出

27

样例 4 输入

12 39916800 8
1 2 3 4 5 6 7 8 9 10 11 12

样例 4 输出

625781677

子任务

对于所有数据，保证 $1\le l\le n\le 100，1\le a_i \le m \le 10^{11}$。