有 N 人，编号为 1 至 N 。昨天他们站成一排，但现在他们不知道自己站的顺序。但是，每个人都记得以下事实：站在他左边的人数与站在他右边的人数的绝对差值。根据他们的报告， i 的上述差值为 A_i 。

根据这些报告，找出他们可能的站位顺序数。由于数字可能非常大，请打印答案，模数为 10^9+7 。请注意，这些报告可能是错误的，因此可能没有一致的顺序。在这种情况下，请打印 0 。

输入内容由标准输入法提供，格式如下

N
A_1 A_2 ... A_N

打印它们可能的排列顺序数，取模 10^9+7 。

对于样例一 有以下四种可能的顺序

• 2,1,4,5,3
• 2,5,4,1,3
• 3,1,4,5,2
• 3,5,4,1,2 对于样例二 任何顺序都会与报告不一致，因此答案为 0 。 数据范围:
• 1≦N≦10^5
• 0≦A_i≦N-1