AT_arc066_a.[ABC050C] Lining Up

有 $N$ 个人，编号为 $1$ 到 $N$。他们昨天以某种顺序排成一列，但今天已经忘记了具体的排列顺序。不过，每个人都记得“自己左边的人数和右边的人数的差的绝对值”。据他们所说，第 $i$ 个人记得的这个差的绝对值为 $A_i$。

请根据他们的报告，求可能的原排列方式有多少种。由于答案可能非常大，请输出答案对 $10^9+7$ 取模的结果。如果他们的报告有误，导致不存在可能的排列方式，请输出 $0$。

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出可能的原排列方式数对 $10^9+7$ 取模的结果。

限制条件

• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq N-1$

样例解释 1

可能的排列方式（以人的编号表示）有：

• $2,1,4,5,3$
• $2,5,4,1,3$
• $3,1,4,5,2$
• $3,5,4,1,2$

共 $4$ 种。

样例解释 2

无论怎样排列，都会与报告矛盾，因此答案为 $0$。

由 ChatGPT 4.1 翻译