配点 : $300$ 点

問題文

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

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

制約

• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq N-1$

入力

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

$N$

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

出力

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

5
2 4 4 0 2

4

ありうる並び方は、人の番号で書くと、

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

の $4$ 通りです。

7
6 4 0 2 4 0 2

0

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

8
7 5 1 1 7 3 5 3

16