問題文

数直線上に，$N$ 枚のコインがあります．$i$ 枚目のコインは座標 $c_i$ にあります．どの $2$ つのコインのある座標も，互いに相異なります．

あなたは，最初座標 $0$ にいます．あなたは，正または負の方向に距離 $1$ だけ移動することを，何度でも行えます．

あなたは，コインのある座標と同じ座標にいるとき，またそのときに限りそのコインを獲得できます．

あなたの目標は，全てのコインを集めて，最後に座標 $0$ に戻ってくることです．ここで，目標を達成するのに必要な移動距離の合計としてありうる最小値を，$M$ とします．

全てのコインを獲得する順序は $N!$ 通りあります．その中で，移動距離の合計が $M$ となる移動の方法が存在するコインの獲得順序の数を，$998244353$ で割った余りを求めてください．

制約

• 入力は全て整数
• $1 \leq N \leq 10^5$
• $-10^8 \leq c_1 < c_2 < \dots < c_N \leq 10^8$

入力

入力は以下の形式で標準入力から与えられる．

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

出力

移動距離の合計が $M$ となる移動の方法が存在するコインの獲得順序を，$998244353$ で割った余りを出力せよ．

サンプル

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