题目描述

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

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

输入格式

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

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

输出格式

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

样例 1

输入

5
2 4 4 0 2

输出

4

样例 2

输入

7
6 4 0 2 4 0 2

输出

0

样例 3

输入

8
7 5 1 1 7 3 5 3

输出

16

说明/提示

限制条件

• $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 翻译