分数: 300 点
问题陈述
有 N 人,方便编号 1 通过 N。 昨天他们站成一排,但现在他们已经不确定自己站的顺序了。 但每个人都记住了一个事实:站在自己左边的人数和站在自己右边的人数的绝对差。 根据他们的报告,上述差异对于人来说 i is 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