Contest Duration: - (local time) (100 minutes) Back to Home
C - Lining Up /

Time Limit: 2 sec / Memory Limit: 256 MB

### 問題文

1～N までの番号がついた、N 人の人がいます。 彼らは昨日、ある順番で左右一列に並んでいましたが、今日になってその並び方が分からなくなってしまいました。 しかし、彼らは全員、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」を覚えています。 彼らの報告によると、人 i の、「自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値」は A_i です。

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

### 入力

N
A_1 A_2 ... A_N


### 入力例 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

4 通りです。

### 入力例 2

7
6 4 0 2 4 0 2


### 出力例 2

0


どのような並び方でも、報告と矛盾するので、0 が答えになります。

### 入力例 3

8
7 5 1 1 7 3 5 3


### 出力例 3

16


Score : 300 points

### Problem Statement

There are N people, conveniently numbered 1 through N. They were standing in a row yesterday, but now they are unsure of the order in which they were standing. However, each person remembered the following fact: the absolute difference of the number of the people who were standing to the left of that person, and the number of the people who were standing to the right of that person. According to their reports, the difference above for person i is A_i.

Based on these reports, find the number of the possible orders in which they were standing. Since it can be extremely large, print the answer modulo 10^9+7. Note that the reports may be incorrect and thus there may be no consistent order. In such a case, print 0.

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

### Input

The input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N


### Output

Print the number of the possible orders in which they were standing, modulo 10^9+7.

### Sample Input 1

5
2 4 4 0 2


### Sample Output 1

4


There are four possible orders, as follows:

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

### Sample Input 2

7
6 4 0 2 4 0 2


### Sample Output 2

0


Any order would be inconsistent with the reports, thus the answer is 0.

### Sample Input 3

8
7 5 1 1 7 3 5 3


### Sample Output 3

16