精灵心目中亘古永恒的能量核心崩溃的那一刻，$Bzeroth$ 大陆的每个精灵都明白，他们的家园已经到了最后的时刻。

就在这危难关头，诸神天降神谕，传下最终兵器——潘少拉魔盒。

然而当精灵们准备打开魔盒时，魔盒的守护灵出现在精灵们面前：

“如果你们想要拯救世界，必须要先解决这个困难的问题：定义一个 $N$ 阶数列 $A$ 为神奇数列当且仅当对所有$2 \leq i \leq N - 1$，都有 $2A_i \leq A_{i-1} + A_{i+1} $。现在有一个 $N$ 阶正整数列 $B$，请计算将 $B$ 数列均匀随机打乱之后，得到的数列是神奇数列的概率 $P$。

你只需要输出 $P × N!$ 对 $998244353$ 取模的结果即可。（显然 $P × N!$ 一定是个整数）。”

输入格式

第一行一个正整数 $N$。

第二行 $N$ 个正整数，第 $i$ 个数为 $A_i$。

输出格式

输出 $P × N!$ 对 $998244353$ 取模的结果。

样例

input

4
1 2 1 3

output

8

explanation

在所有 $24$ 种排列中，共有 $8$个数列是合法的： $ {1 1 2 3} $、 $ {1 1 2 3} $、 $ {2 1 1 3} $、 $ {2 1 1 3} $、 $ {3 1 1 2} $、 $ {3 1 1 2} $、 $ {3 2 1 1} $、 $ {3 2 1 1} $ 。

限制与约定

对于 $50\texttt{%}$ 的数据：$3 \leq N \leq 10$。

对于 $80\texttt{%}$ 的数据：$3 \leq N \leq 20$。

对于 $100\texttt{%}$ 的数据：$3 \leq N \leq 40$，$1 \leq A_i \leq 10^9$ 。

时间限制：$1\texttt{s}$

空间限制：$128\texttt{MB}$