U470963 差分回文数列

对于一个数列 $\{a_n\}$，定义他的差分数列 $\{d_n\}=\{a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}\}$，数列 $\{a_n\}$ 被称作“差分回文数列”，当且仅当他的差分数列是一个回文数列。 现给出数列 $\{a_n\}$，问有多少种重排方式，使得 $\{a_n\}$ 重排后是一个“差分回文数列”，答案对 $998244353$ 取模。 两种重排方式不同，当且仅当重排后形成的两个数列不同。

第一行一个整数 $n$，表示数列长度。 第二行 $n$ 个整数，第 $i$ 个表示 $a_i$。

一个整数，表示重排方式对 $998244353$ 取模的答案。

**【样例 1 解释】** 合法的“差分回文数列”有 `1 2 3` 和 `3 2 1` 两种，其差分数列分别为 `1 1` 和 `-1 -1`。 **【样例 2 解释】** 无论怎么重排，数列均为 `3 3 3`，差分数列为 `0 0`。 **【样例 3 解释】** 找不到满足条件的重排方案。 **【数据范围】** 对于所有测试数据有：$2 \leq n \leq 10^6,1\leq a_i\leq 10^9$。 | 测试点 | $n\leq$ |$a_i \leq$| 特殊性质 | | :----------: | :----------: |:----------: | :----------: | | $1\sim 3$ | $10$ |$100$| 无 | | $4\sim 5$ | $500$ |$10^4$| 无 | | $6$ | $10^4$ |$10^6$| A | | $7$ | $10^4$ |$10^6$| B | | $8\sim 10$ | $10^6$ |$10^9$| 无 | 特殊性质 A：序列中只有三种数。 特殊性质 B：序列是 $1\sim n$ 的排列。