问题描述

有 $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$。

5
2 4 4 0 2

4

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

$2,1,4,5,3$

$2,5,4,1,3$

$3,1,4,5,2$

$3,5,4,1,2$

7
6 4 0 2 4 0 2

0

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

8
7 5 1 1 7 3 5 3

16

注：模mod即取余%运算，其对加减乘封闭且相容（即取值范围一致、同余关系在加减乘下被保持）。

如：$27\%4+33\%4=(27\%4+33\%4)\%4$

$[A+B]\%m=[(k_Am+b_A)+(k_Bm+b_B)]\%m=(b_A+b_B)\%m$

$[A\%m+B\%m]\%m=[(k_Am+b_A)\%m+(k_Bm+b_B)\%m]\%m=(b_A+b_B)\%m$

如：$3*7*6*9*12\%4=3*7\%4*6\%4*9\%4*12\%4$

$[A*B]\%m=[(k_Am+b_A)*(k_Bm+b_B)]\%m=[k_Ak_Bm^2+(k_Ab_B+k_Bb_A)m+b_Ab_B]\%m=b_Ab_B\%m$

$(A\%m)*(B\%m)\%m=[(k_Am+b_A)]\%m*[(k_Bm+b_B)\%m]\%m=b_Ab_B\%m$

你可以在本地用计算器按一下下面两个计算过程进行对比，显然前者需要保存更大的结果，超出了 int

$123456789*987654321\%13579$ 和 $(123456789\%13579)*(987654321\%13579)\%13579$

本题取模的目的是为了避免过大的计算结果，通过取模将其控制在较小范围内。你只需要一边计算一边取模即可。