Problem:
 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

Solution (Python):
import math
N = int(input())
A = list(map(int, input().split()))
M = math.ceil(N / 2)
L = [0 for i in range(M)]

for a in A:
    if (N % 2 == 0 and a % 2 == 0) or (N % 2 != 0 and a % 2 != 0):
        print(0)
        exit()
    L[M - a // 2 - 1] += 1

if N % 2 == 0:
    for m in range(M):
        if L[m] != 2:
            print(0)
            exit()
else:
    for m in range(M):
        if m != M - 1:
            if L[m] != 2:
                print(0)
                exit()
        else:
            if L[m] != 1:
                print(0)
                exit()

ans = 1
MOD = int(1e9) + 7
for m in range(N // 2):
    ans *= 2
    ans %= MOD
print(ans)

Solution (Python):
import sys
n=int(input())
array=list(map(int, input().split()))

if not (0<=min(array) and max(array)<n):
    print(0)
    sys.exit()

if n%2==0:
    if (n**2)/2 != sum(array):
        print(0)
        sys.exit()
else:
    if (n**2-1)/2 != sum(array):
        print(0)
        sys.exit()

sub_list=list(set(array))

if n%2==0:
    if int(n/2)==len(sub_list):
        print((2 ** int(n / 2))%(10**9 + 7))
    else:
        print(0)
else:
    if int(n/2)==len(sub_list)-1:
        print((2 ** int(n / 2)) % (10 ** 9 + 7))
    else:
        print(0)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
A.sort()

if N % 2 == 0:
    C = []
    for c in [2*i+1 for i in range(N//2)]:
        C += [c] * 2
    if A == C:
        print(2**(N//2) % (10**9 + 7))
    else:
        print(0)
else:
    C = [0]
    for c in [2*i for i in range(1, N//2 + 1)]:
        C += [c] * 2
    if A == C:
        print(2**(N//2) % (10**9 + 7))
    else:
        print(0)

Solution (Python):
def pow(base, nod):
  MOD = 10**9+7
  ans = 1
  tmp = base
  while nod>0:
    if nod%2==1: ans=ans*tmp%MOD
    tmp = tmp**2
    tmp %= MOD
    nod /= 2
  return ans

n=int(raw_input())
a=map(int,raw_input().split())
d={}
for i in xrange(n):
  if a[i] not in d: d[a[i]]=0
  d[a[i]]+=1
isValid=True
if n%2==0:
  for k,v in d.items():
    if k%2!=1 or v!=2:
      isValid=False
else:
  for k,v in d.items():
    if k%2!=0 or (k==0 and v!=1) or (k!=0 and v!=2):
      isValid=False
if isValid:
  print pow(2, n/2)
else:
  print 0

Solution (Python):
from collections import defaultdict
n=int(input())
arr=list(map(int,input().split()))
dd=defaultdict(int)
for a in arr:
    dd[a]+=1
if n%2==0:
    for i in range(1,n,2):
        if dd[i]!=2:
            print(0)
            exit(0)
    else:
        prod=1
        for i in range(n//2):
            prod*=2
            prod%=1000000007
        print(prod)
else:
    if dd[0]!=1:
        print(0)
        exit(0)
    for i in range(2,n,2):
        if dd[i]!=2:
            print(0)
            exit(0)
    else:
        prod=1
        for i in range((n-1)//2):
            prod*=2
            prod%=1000000007
        print(prod)

Solution (Python):

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
m = n // 2
ca = Counter(a)

if n % 2 == 1 and ca[0] == 1 and all(ca[(i+1)*2] == 2 for i in range(m)):
    ans = (2 ** m) % (10 ** 9 + 7)
    print(ans)
elif n % 2 == 0 and all(ca[i*2 + 1] == 2 for i in range(m)):
    ans = (2 ** m) % (10 ** 9 + 7)
    print(ans)
else:
    print(0)

Solution (Python):
def powmod(b,e,m):
    r=1
    while e>0:
        if e%2==1:
            r=(r*b)%m
        e>>=1
        b=(b*b)%m
    return r

def check(N,d):
    if N%2==0:
        for i in range(1,N,2):
            if i in d:
                if d[i]!=2:
                    return False
            else:
                 return False
    else:
        if 0 in d:
            if d[0]!=1:
                return False
        else:
            return False
        for i in range(2,N,2):
            if i in d:
                if d[i]!=2:
                    return False
            else:
                return False
    return True

N=int(input())
A=list(map(int,input().split()))
d={}

for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1

if check(N,d):
    ans=powmod(2,N//2,10**9+7)
else:
    ans=0
print(ans)

Solution (Python):
import sys


def test(a):
    if len(a) % 2:
        if a[0]:
            return False

        del a[0]

    for i in range(0, len(a) - 2, 2):
        if a[i] != a[i + 1] or a[i + 2] - a[i] != 2:
            return False

    return True


input()
a = sorted(list(map(int, input().split())))

if a[:2] == [0, 0]:
    print(0)
    sys.exit(0)

elif a == [0]:
    print(1)
    sys.exit(0)

elif a == [0, 1, 1] or a == [1, 1]:
    print(2)
    sys.exit(0)

print((2 ** round(len(a) / 2)) % (10 ** 9 + 7) if test(a) else 0)

Solution (Python):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
M = N//2
c = Counter(A)
if N % 2 == 1 and A.count(0) == 1 and all(c[i*2+2] == 2 for i in range(M)):
    print((2 ** M) % (10**9+7))
elif N % 2 == 0 and all(c[i*2+1]==2 for i in range(M)):
    print((2 ** M) % (10**9+7))
else:
    print(0)

Solution (Python):
def error_check(n,l):
	total = 0
	if n % 2 == 0:
		i = 1
		for k in range(n//2):
			total += (i+i)
			i += 2
		if total == sum(l):
			return True
		else:
			return False
	else:
		i = 2
		for k in range(n//2):
			total += (i+i)
			i += 2
		if total == sum(l):
			return True
		else:
			return False

n = int(input())
a = list(map(int,input().split()))
m = n // 2
if error_check(n,a):
	print((2 ** m) % (10**9+7))
else:
	print(0)

Solution (Python):
N = int(input())
line = list(map(int, input().split()))
n = N - 1
ans = 1
line.sort()
s = len(line)
index = s - 1
while(index > 1):
    if line[index] == n and line[index-1] == n:
        ans *= 2
        n = n - 2
        index = index - 2
    else:
        print(0)
        break

if index == 1:
    if line[index] == n and line[index-1] == n:
        ans *= 2
        print(ans % (10**9+7))
    else:
        print(0)

elif index == 0:
    if line[0] == 0:
        print(ans % (10**9+7))
    else:
        print(0)

Solution (Python):
from sys import stdin
mod=10**9+7
def expo(n):
    if n<=0:
        return 1
    if n%2==0:
        return expo(n//2)*expo(n//2)%mod
    else:
        return 2*expo(n//2)*expo(n//2)%mod

n=int(input())
differences=list(map(int,stdin.readline().split()))
repetition=0
nbDiff=[0]*n
places=[0]*n
possible=True
moitie=n//2
for i in range(n):
    difference=differences[i]
    moitieDiff=difference//2
    if nbDiff[difference]==1:
        repetition+=1
    nbDiff[difference]+=1    
    
    if n%2==1:
        places[moitie+moitieDiff]+=1
        places[moitie-moitieDiff]+=1
    else:
        places[moitie+moitieDiff]+=1
        places[moitie-moitieDiff-1]+=1

for i in range(n):
    if places[i]!=2:
        possible=False

if possible:
    print(expo(repetition))
else:
    print(0)

Solution (Python):
import collections
N=int(input())
B=[]
g=10**9+7
A=[int(i) for i in input().split()]
for i in A:
 B.append(((N-1+i)/2,(N-1-i)/2))
c= collections.Counter(B)
d=1
for i,j in c.items():
 d*=j
 if j==1 and i[0]!=i[1]:
   d=0
   break
 if d>g:
   d=d%g
print(d%g)

Solution (Python):
N = int(raw_input())
A=map(int, raw_input().split(' '))
A.sort()
flug = 0
if N % 2 == 0:
    for i in range(N):
        if not A[i] == 2*(i/2)+1:
            flug = 1
            break

else:
    for i in range(N):
        if i % 2 == 0:
            if not A[i] == i:
                flug =1
                break
        else:
            if not A[i] == i+1:
                flug = 1
                break
if flug == 0:
    print(pow(2, N/2))%(pow(10,9)+7)
else:
    print 0

Solution (Python):
import collections
N=int(raw_input())
A=map(int, raw_input().split())
count_A=collections.Counter(A).most_common(1)
cnt = 0
if N == 1:
    if A[0] == 0:
        print 1
    else:
        print 0
elif N%2 == 0:
    if A.count(0) != 0:
        print 0
        cnt = 1
    elif count_A[0][1] != 2:
        print 0
        cnt = 1
    if cnt == 0:
        print (2**(N/2)) % (10**9+7)
else:
    if A.count(0) != 1:
        print 0
        cnt = 1
    elif count_A[0][1] != 2:
        print 0
        cnt = 1
    if cnt == 0:
        print (2**(N/2)) % (10**9+7)

Solution (Python):


import sys

def main(argv):
    n = sys.stdin.readline().rstrip()

    while n:
        result = -1
        n = int(n)
        count = [0 for i in range(0, int(n / 2))]
        if n % 2 != 0:
            count.append(0)
        a = [int(i) for i in raw_input().split()]
        for a_i in a:
            index, reminder = divmod(a_i, 2)
            if reminder == n % 2 or index >= len(count):
                result = 0
                break
            else:
                count[index] += 1

        if result < 0:
            if n % 2 != 0:
                if count[0] != 1:
                    result = 0
                else:
                    for c in count[1:]:
                        if c != 2:
                            result = 0
                            break
                    if result != 0:
                        result = 2 ** (len(count) - 1)
            else:
                for c in count:
                    if c != 2:
                        result = 0
                        break
                if result != 0:
                    result = 2 ** len(count)
        print result % ((10 ** 9) + 7)

        n = sys.stdin.readline().rstrip()

if __name__ == "__main__":
    main(sys.argv)

Solution (Python):
import collections

num = int(input().rstrip())
line = input().rstrip().split()
line = [int(x) for x in line]

count_dict = collections.Counter(line)

last = 10**9 + 7

num_list = []

ans = 1

if num % 2 == 0:
    for k, v in count_dict.items():
        if v != 2:
            ans = 0

else:
    for k, v in count_dict.items():
        if v != 2 and k != 0:
            ans = 0

if ans == 0:
    print(0)
else:
    print(2**(num // 2) % last)

Solution (Python):
import sys

n = int(input())
a_lst = [int(x) for x in input().split()]

dic = {}

for i in range(1, n + 1, 2):
    j = n - i
    dic[j] = 1 if j == 0 else 2

for i in a_lst:
    if i not in dic:
        print(0)
        sys.exit()

    dic[i] -= 1

    if dic[i] < 0:
        print(0)
        sys.exit()

print(pow(2, n // 2) % (pow(10, 9) + 7))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]
res = 1

for i in a:
    b[i] += 1

if n % 2 == 1:
    if b[0] != 1:
        print(0)
        exit(0)
    else:
        for i in range(2, n, 2):
            if b[i] != 2:
                print(0)
                exit(0)
            
            res = res * 2 % (10**9 + 7)
else:
    for i in range(1, n, 2):
        if b[i] != 2:
            print(0)
            exit(0)
        res = res * 2 % (10 ** 9 + 7)
print(res)

Solution (Python):
def main():
	n = input()
	p = map(int, raw_input().split())
	p.sort()

	lia = []
	lib = []
	if(n % 2 == 0):
		for i in range(0,n,2):
			if(p[i] != p[i+1]):
				print 0
				return
			if(p[i] != i+1):
				print 0
				return
			lia.append(p[i])
			lib.append(p[i+1])
	else:
		for i in range(1, n, 2):
			if(p[i] != p[i+1]):
				print 0
				return
			if(p[i] != i+1):
				print 0
				return
			lia.append(p[i])
			lib.append(p[i+1])

	print 2**(n/2) % (10**9 + 7)

if __name__ == "__main__":
	main()

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
f=True
if n%2==0:
    for i in range(n):
        if a[i]!=i//2*2+1:
            f=False
            break
else:
    for i in range(n):
        if a[i]!=(i+1)//2*2:
            f=False
            break
print(2**(n//2)%(10**9+7) if f else 0)

Solution (Python):

N = int(input())
st = input().split()
d = 10**9 + 7
A = []
m = N%2
fl = {}
exflag = False
for i in range(N):
    a = int(st[i])
    A.append(a)
    if (a + m) % 2 == 0:
        print(0)
        exflag = True
        break
    if a == 0:
        if 0 in fl.keys():
            print(0)
            exflag = True
            break
        fl[0] = 1
    else:
        if a in fl.keys():
            if fl[a] > 1:
                print(0)
                exflag = True
                break
            else:
                fl[a] = 2
        else:
            fl[a] = 1

        
if exflag == False:    
    ret = 2**(N//2) %d
    print(ret)

Solution (Python):

N = int(input())
A = list(map(int, input().split()))

A_ = sorted(A)

if len(A_) == 1:
    if A_[0] == 0:
        print(1)
    else:
        print(0)

elif A_[0] == A_[1] == 0:
    print(0)

else:
    ans_ = 2 ** (N // 2)
    ans = ans_ % (10**9 + 7)


    if len(A_) % 2 == 0:
        for i in range(len(A_) // 2):
            if A_[2*i] != A_[2*i+1]:
                print(0)
                exit()

    else:
        if A_[0] != 0:
            print(0)
            exit()

        for i in range(len(A_) // 2):
            if A_[2*i+1] != A_[2*i+2]:
                print(0)
                exit()


    print(ans)

Solution (Python):
n = input()
a = map(int, raw_input().split())
a.sort()
ok = 0


if n % 2 == 1:
	for i in range(len(a)):
		if (i % 2 == 0 and a[i] != i) or (i % 2 == 1 and a[i] != i + 1):
			print 0
			ok = 1
			break

if n % 2 == 0:
	for i in range(len(a)):
		if (i % 2 == 1 and a[i] != i) or (i % 2 == 0 and a[i] != i + 1):
			print 0
			ok = 1
			break

if ok == 0:
	
	print pow((2 % 1000000007), ((n / 2) % 1000000006)) % 1000000007

Solution (Python):

import math
import string
import time
import fractions









n = int(raw_input())
a = map(int, raw_input().split())

a.sort()
ret = -1
if n % 2 == 0:
	for i in range(n):
		tmp = i
		if i % 2 == 0:
			tmp += 1
		if tmp != a[i]:
			ret = 0
			break
	if ret == -1:
		ret = (2 ** (n / 2)) % (10 ** 9 + 7)
else:
	for i in range(n):
		tmp = i
		if i % 2 == 1:
			tmp += 1
		if tmp != a[i]:
			ret = 0
			break
	if ret == -1:
		ret = (2 ** (n / 2)) % (10 ** 9 + 7)

print ret

Solution (Python):
n = int(raw_input())
a = [int(x) for x in raw_input().split()]

c = {}

for v in a:
    if v not in c:
        c[v] = 0
    c[v] += 1

d = {i: 1 if i == 0 else 2 for i in xrange(1 - n % 2, n, 2)}

MOD = 10**9 + 7

if c == d:
    print pow(2, n // 2, MOD)
else:
    print 0