Ena 和 Mizuki 正在玩一个游戏。

桌上有 $n$ 个物品，编号从 $1$ 到 $n$。第 $i$ 个物品的价值为 $a_i$。Ena 和 Mizuki 轮流进行操作，Ena 先手。在每一轮中，玩家选择一个尚未被取走的物品并将其取走。当所有物品都被取走时，游戏结束。双方的目标都是最大化自己所取走物品的价值总和。

已知双方均采取最优策略，请问有多少种可能的对局过程？由于结果可能很大，请输出其对 $998\,244\,353$ 取模的结果。

如果存在某个整数 $i$ ($1 \le i \le n$)，使得第 $i$ 轮取走的物品编号不同，则认为这两个过程是不同的。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

输出格式

输出答案。

样例

样例输入 1

3
1 2 2

样例输出 1

4

样例输入 2

6
1 3 2 2 3 1

样例输出 2

120

样例输入 3

12
1 1 4 5 1 4 1 9 1 9 8 10

样例输出 3

28800

说明

在第一个样例中，有四种可能的对局过程：

• $[1, 2, 3]$。
• $[1, 3, 2]$。
• $[2, 3, 1]$。
• $[3, 2, 1]$。

这里 $[a, b, c]$ 表示第一轮 Ena 取走第 $a$ 个物品，第二轮 Mizuki 取走第 $b$ 个物品，最后一轮 Ena 取走第 $c$ 个物品。

注意 $[2, 1, 3]$ 不是一个可能的对局过程，因为第二轮对于 Mizuki 而言不是最优策略。