← 返回题目列表

AtCoder · arc066_a

C. 排队

中文机器翻译题面 查看原题

分数: 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