N class students, conveniently numbered from
1 to
N. On the ruler on September 1, they stood in a row, but now they are not sure in what order they stood. However, everyone remembered the following fact: the absolute difference between the number of students who stood to the left of this person and the number of students who stood to the right of this person. According to their reports, the difference for a human
i is
Ai . Based on these reports, find the number of possible arrangements in which they stood. Because the answer can be very large, print it modulo
\(10^9+7\). Please note that the reports may not be correct and therefore there may not be a consistent order. In this case, print
0.
Input
The first line specifies the number
N (
\(1<=N<=10^5\)). In the second line
N numbers
Ai (
\(0<=A_i<=N -1\)).
Imprint
Print the number of possible arrangements modulo
\(10^9+7\).
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
2 4 4 0 2
| 4 |
There are 4 possible arrangements of students, namely:
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
| 0 |
Any spacing is not compatible with reports. So the answer is 0. |
| 3 |
8
7 5 1 1 7 3 5 3
| 16 |
|