Problem Statement

There are $N$ coins on a number line. The $i$-th coin is at coordinate $c_i$. No $2$ coins are at the same coordinate.

You are initially at coordinate $0$. You may move a distance of $1$ in the positive or negative direction any number of times.

You can obtain a coin if and only if you are at the same coordinate as that coin.

Your goal is to collect all the coins and finally return to coordinate $0$. Let $M$ be the minimum possible total distance traveled needed to achieve this goal.

There are $N!$ orders in which all the coins can be obtained. Among them, find the number, modulo $998244353$, of orders of obtaining the coins for which there exists a way of moving with a total distance traveled of $M$.

Constraints

• All inputs are integers
• $1 \leq N \leq 10^5$
• $-10^8 \leq c_1 < c_2 < \dots < c_N \leq 10^8$

Input

The input is given from Standard Input in the following format.

$N$
$c_1$ $c_2$ $\dots$ $c_N$

Output

Output the number, modulo $998244353$, of orders of obtaining the coins for which there exists a way of moving with a total distance traveled of $M$.

Sample

3
-1 1 3

4

5
-2 -1 0 1 2

24

37
-32 -30 -28 -27 -25 -24 -22 -20 -18 -17 -15 -13 -10 -9 -8 -5 -3 -2 1 3 6 7 8 9 11 12 14 16 19 22 23 24 26 28 30 32 36

838860732