该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

输入格式

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

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

其中：

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

输出格式

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

样例

5
2 4 4 0 2

4

样例解释 1

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

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

共 $4$ 种。

7
6 4 0 2 4 0 2

0

样例解释 2

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

8
7 5 1 1 7 3 5 3

16