题目描述

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

彼らの報告を元に、元の並び方が何通りあり得るかを求めてください。 ただし、答えは非常に大きくなることがあるので、$10^9+7$ で割った余りを出力してください。 また、彼らの報告が間違っており、ありうる並び方がないこともありえます。 その際は $0$ を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ $...$ $A_N$

输出格式

元の並び順としてありうるものが何通りあるか求め、$10^9+7$ で割った余りを出力せよ。

题目大意

有编号为1-N号的N个人，他们都记得“自己左边排队的人数和自己右边排队的人数之差的绝对值”，根据他们的报告，给你i的「自己的左排列的人数和自己的右排列的人数的差的绝对值」Ai。 请根据他们的报告，求出原来的排列方法有几种。但是，因为答案有时候会变得很大，请对10^9+7取模 。另外，他们的报告可能有错误，没有可能的排列方法，此时请输出0。

范围：

5
2 4 4 0 2

4

7
6 4 0 2 4 0 2

0

8
7 5 1 1 7 3 5 3

16

提示

制約

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

Sample Explanation 1

ありうる並び方は、人の番号で書くと、 - $2,1,4,5,3$ - $2,5,4,1,3$ - $3,1,4,5,2$ - $3,5,4,1,2$ の $4$ 通りです。

Sample Explanation 2

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