You are working on a math problem.

You believe the final answer can be obtained by $a_1 \times a_2 \times \cdots \times a_n$, so you calculated this product.

However, you discover that the correct answer is $m$.

You believe the form of the answer is correct, and the problem might lie in the fact that some of the terms $a_i$ were calculated incorrectly.

The correct factorization should be in the form $m = b_1 \times b_2 \times \cdots \times b_n$, where at least one $b_i$ is different from $a_i$. At the same time, you hope that you did not calculate too many terms $a_i$ incorrectly, meaning that at most $l$ terms $b_i$ are different from $a_i$.

You want to know how many ordered sequences $b_1, b_2, \cdots, b_n$ satisfy these requirements. If there is exactly one correct factorization, then there is no need to recheck from the beginning.

Input

The first line of input contains three positive integers $n, m, l$, representing the number of terms in the product, the correct product, and the maximum number of terms that could be calculated incorrectly, respectively. It is guaranteed that $1 \le l \le n \le 100$ and $1 \le m \le 10^{11}$.

The second line of input contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the original terms. It is guaranteed that $1 \le a_i \le m$.

Output

Output a non-negative integer representing the number of possible factorizations modulo $998,244,353$.

Examples

Input 1

3 18 1
3 3 3

Output 1

3

Note 1

The possible factorizations are $2\times 3\times 3$, $3\times 2\times 3$, and $3\times 3\times 2$.

Input 2

3 20240414 2
24 4 14

Output 2

0

Note 2

$20240414 = 2\times 23\times 440009$, so no factorization satisfying the requirements exists.

Input 3

3 20240414 3
24 4 14

Output 3

27

Input 4

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

Output 4

625781677

Subtasks

For all test cases, it is guaranteed that $1 \le l \le n \le 100$ and $1 \le a_i \le m \le 10^{11}$.