Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given an integer sequence $A_{1}, A_{2}, \ldots, A_{N}$. Find the number of integer sequences $X_{1}, X_{2}, \ldots, X_{N}$ such that
$0 ≤ X_{i} < 239$ for each valid $i$
$X_{i} \neq X_{j}$ for each valid $i \neq j$
$(X_{1} \cdot A_{1}) + (X_{2} \cdot A_{2}) + \ldots + (X_{N} \cdot A_{N})$ is divisible by $239$

Since the answer may be large, compute it modulo $998,244,353$.

------ Input ------
The first line of the input contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------ Output ------
Print a single line containing one integer ― the number of sequences satisfying all conditions modulo $998,244,353$.

------ Constraints ------
$1 ≤ N ≤ 20$
$0 ≤ A_{i} < 239$ for each valid $i$

------ Subtasks ------
Subtask #1 (10 points): $N ≤ 10$

Subtask #2 (10 points): $N ≤ 15$

Subtask #3 (80 points): original constraints

----- Sample Input 1 ------
3

1 1 1
----- Sample Output 1 ------
56406

见题面

见题面