/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
1～N までの番号がついた、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
の 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.
Constraints
- 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