问题描述

有 $N$ 个人，方便地编号为 $1$ 到 $N$。昨天他们站成一列，但现在他们不确定他们的站立顺序。然而，每个人记得以下事实：左边站着的人数与右边站着的人数之差的绝对值。根据他们的报告，第 $i$ 个人的差异是 $A_i$。

根据这些报告，找出他们可能站立的顺序的数量。由于可能非常大，请将答案打印后以 $10^9+7$ 取模。请注意，报告可能是错误的，因此可能没有一致的顺序。在这种情况下，请打印 $0$。

约束条件

• $1≦N≦10^5$
• $0≦A_i≦N-1$

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $A_2$ $...$ $A_N$

输出

打印可能站立的顺序的数量，以 $10^9+7$ 取模。

示例输入 1

5
2 4 4 0 2

示例输出 1

4

有四种可能的顺序，如下所示：

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

示例输入 2

7
6 4 0 2 4 0 2

示例输出 2

0

任何顺序都与报告不一致，因此答案为 $0$。

示例输入 3

8
7 5 1 1 7 3 5 3

示例输出 3

16