Welcome to the exciting class of Professor Manasa. In each lecture she used to play some game while teaching a new concept. Today's topic is Set Theory. For today's game, she had given a set A = {a_{1}, a_{2}, ...a_{N}} of N integers to her students and asked them to play the game as follows.  

At each step of the game she calls a random student and asks him/her to select a non-empty subset from set A such that this subset had not been selected earlier and the sum of subset should be even. This game ends when all possible subsets had been selected. Manasa needs your help in counting the total number of times students can be called assuming each student gives the right answer. While it is given that if two numbers are same in the given set, they have different colors. It means that if a1 = a2, then choosing a1 and choosing a2 will be considered as different sets. 

Note  

Two subsets are different if there exists an element (a_{k}) that is present in one subset but not in other. Let's say set A = {a_{1}, a_{2}, a_{3}} = {2, 2, 3}, then all possible subsets are {}, {a_{1}}, {a_{2}}, {a_{3}}, {a_{1}, a_{2}}, {a_{1}, a_{3}}, {a_{2}, a_{3}}, {a_{1}, a_{2}, a_{3}} which is equivalent to {}, {2}, {2}, {3}, {2, 2}, {2, 3}, {2, 3}, {2, 2, 3}.  

Students can be called multiple times.  

Input Format 

The first line contains an integer N i.e. size of set A. 

Next line will contain N integers, each representing an element of A.  

Output Format 

Print number of time students are called. As this number can be very large you have to print the answer modulo (10^{9} + 7). 

Constraints 

1 ≤ N ≤ 10^{5} 

0 ≤ a_{i} ≤ 10^{4} , where i ∈ [1 .. N]

Sample Input 00  

4
2 4 6 1

Sample Output 00  

7

Sample Input 01  

3
1 2 2

Sample Output 01  

3

Explanation 

There are 7 different ways in which a non-empty subset, with even sum, can be selected, i.e., {2}, {4}, {6}, {2, 4}, {2, 6}, {4, 6}, {2, 4, 6}.

For second sample test case, there are 3 different ways in which a non-empty subset, with even sum, can be selected, i.e., {a_{2}}, {a_{3}}, {a_{2}, a_{3}} which is equivalent to {2}, {2}, {2,2}.

Difficulty: EASY
Tags: Combinatorics

Starter code:

Solutions:
mod = 1000000007
n = int(input())
A = list(map(int, input().split(' ')))
odd = len([x for x in A if x % 2 == 1])
even = n - odd
if odd == 0:
	odd = 1
print((2 ** (odd - 1) % mod * (2 ** even % mod) - 1) % mod)


mod = 10 ** 9 + 7
N = int(input())
A = [int(x) for x in input().split()]
oddcount = 0
res = 0
K = 1
D = 1
for x in A:
	if x % 2 == 0:
		K = K * 2 % mod
	else:
		oddcount += 1
res += K - 1
D = 1
for i in range(oddcount + 1):
	D = D * (oddcount - i) % mod
	D = D * pow(i + 1, mod - 2, mod) % mod
	if i % 2 == 1:
		res = (res + D * K) % mod
print(res)


m = 10 ** 9 + 7
n = int(input())
c0 = 0
c1 = 0
data = input().rstrip().split()
for i in range(n):
	c = int(data[i])
	if c % 2 == 0:
		c0 += 1
	else:
		c1 += 1
evens = (2 ** c0 - 1) % m if c0 > 0 else 0
odds = (2 ** (c1 - 1) - 1) % m if c1 > 0 else 0
full = (evens + odds + evens * odds % m) % m
print(str(full))


N = int(input())
A = input().split()
p = 0
for i in range(N):
	p = min(1, p + int(A[i]) % 2)
print(2 ** (N - p) % (10 ** 9 + 7) - 1)


mod = 1000000007
n = int(input())
a = [int(x) % 2 for x in input().split()]
e = 0
o = 0
for v in a:
	if v == 0:
		e += 1
	else:
		o += 1
a = pow(2, e, mod) - 1
if o == 0:
	b = 0
else:
	b = pow(2, o - 1, mod) - 1
print((a + b + a * b) % mod)


N = int(input())
ns = input()
num = ''
evens = 0
odds = 0
mod = 10 ** 9 + 7
for n in ns:
	if n.isdigit():
		num += n
	else:
		num = int(num)
		if num % 2 == 0:
			evens += 1
		else:
			odds += 1
		num = ''
else:
	num = int(num)
	if num % 2 == 0:
		evens += 1
	else:
		odds += 1
total = 2 ** evens
if odds > 0:
	total = total * 2 ** (odds - 1) if total > 0 else 2 ** (odds - 1) - 1
total -= 1
print(total % mod)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


N = int(input())
A = [int(x) for x in input().split(' ')]
(nbEven, nbOdd) = (0, 0)
for a in A:
	if a % 2 == 0:
		nbEven += 1
	else:
		nbOdd += 1
MOD = 10 ** 9 + 7
(s, c, i) = (0, 1, 0)
while i <= nbOdd:
	s = (s + c) % MOD
	c = c * (nbOdd - i) * (nbOdd - i - 1) // (i + 1) // (i + 2)
	i += 2
s *= pow(2, nbEven, MOD)
s = (s - 1) % MOD
print(s)


totnums = int(input())
nums = input().split(' ')
for i in range(len(nums)):
	nums[i] = int(nums[i])
neven = 0
for i in nums:
	if i % 2 == 0:
		neven += 1
nodd = totnums - neven
if nodd == 0:
	nodd = 1
pows = neven + nodd - 1
ans = 1
for i in range(pows):
	ans *= 2
	if ans >= 7 + 1000000000.0:
		ans %= int(7 + 1000000000.0)
ans -= 1
print(ans)


t = int(input())
a = int(1000000000.0) + 7
l = input().strip().split()
odd = 0
even = 0
for i in l:
	if int(i) % 2 == 0:
		even += 1
	else:
		odd += 1
if odd == 0:
	r = pow(2, even, a)
else:
	r = pow(2, even, a) * pow(2, odd - 1, a) % a
print(r - 1)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


MOD = 10 ** 9 + 7
N = int(input())
A = [int(_) for _ in input().split(' ')]
(nbe, nbo) = (0, 0)
for a in A:
	if a & 1:
		nbo += 1
	else:
		nbe += 1
ce = pow(2, nbe, MOD)
if nbo > 0:
	co = pow(2, nbo - 1, MOD)
else:
	co = 1
print((ce * co - 1) % MOD)


import sys
n = int(sys.stdin.readline().strip())
data = sys.stdin.readline().strip().split()
even = 0
odd = 0
mod = 10 ** 9 + 7
for x in data:
	if int(x) % 2 == 0:
		even = even + 1
	else:
		odd = odd + 1
ans = 0
if odd == 0:
	ans = pow(2, even + odd, mod) - 1
else:
	ans = pow(2, even + odd - 1, mod) - 1
print(ans)


class Chocolate:

	def __init__(self):
		self.total = 0
		self.has_odd = False

	def add(self, n):
		if n % 2:
			self.add_odd()
		else:
			self.add_even()

	def add_even(self):
		self.total = self.total * 2 + 1

	def add_odd(self):
		if self.has_odd:
			self.total = self.total * 2 + 1
		else:
			self.has_odd = True
N = int(input())
ar = [int(n) for n in input().split()]
choc = Chocolate()
for n in ar:
	choc.add(n)
print(choc.total % (10 ** 9 + 7))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


N = int(input())
sq = [int(i) for i in input().split(' ')]
even = 0
odd = 0
for x in sq:
	if x % 2 == 0:
		even += 1
	else:
		odd += 1
MOD = 10 ** 9 + 7
x = (2 ** even - 1) % MOD
y = (2 ** (odd - 1) - 1) % MOD if odd > 0 else 0
print((x + y + x * y) % MOD)


mod = 10 ** 9 + 7
n = int(input())
a = [int(x) for x in input().split()]
nr_odd = len(list(filter(lambda x: x % 2 == 1, a)))
if nr_odd == 0:
	print((pow(2, n, mod) - 1) % mod)
else:
	print((pow(2, n - 1, mod) - 1) % mod)


def getSubCnt(arr, lft, rgt):
	if lft == rgt:
		if arr[lft] % 2 == 0:
			return [0, 1]
		else:
			return [1, 0]
	mid = (lft + rgt) // 2
	ans1 = getSubCnt(arr, lft, mid)
	ans2 = getSubCnt(arr, mid + 1, rgt)
	ans = [0, 0]
	ans[0] = ans1[0] + ans2[0]
	ans[1] = ans1[1] + ans2[1]
	ans[0] += ans1[0] * ans2[1] + ans1[1] * ans2[0]
	ans[1] += ans1[0] * ans2[0] + ans1[1] * ans2[1]
	ans[0] = ans[0] % 1000000007
	ans[1] = ans[1] % 1000000007
	return ans
N = int(input())
line = input().split()
arr = []
for num in line:
	arr.append(int(num))
ans = getSubCnt(arr, 0, N - 1)
print(str(ans[1]))


import math
__author__ = 'max'

def main():
	num_elements = int(input())
	num_evens = sum((1 for e in input().split() if int(e) % 2 == 0))
	num_odds = num_elements - num_evens
	num_even_subsets_only_even_elements = 2 ** num_evens - 1
	if num_odds == 0:
		num_even_subsets_only_odd_elements = 0
	else:
		num_even_subsets_only_odd_elements = 2 ** num_odds // 2 - 1
	num_even_subsets_both_even_and_odd = num_even_subsets_only_even_elements * num_even_subsets_only_odd_elements
	print((num_even_subsets_both_even_and_odd + num_even_subsets_only_even_elements + num_even_subsets_only_odd_elements) % (10 ** 9 + 7))
main()


import itertools
n = int(input().strip())
l = [int(x) for x in input().strip().split()]
nEven = 0
nOdd = 0
for i in range(0, len(l)):
	if l[i] % 2 == 0:
		nEven += 1
	else:
		nOdd += 1
if nOdd == 0:
	print((2 ** nEven - 1) % 1000000007)
else:
	print((2 ** nEven * 2 ** (nOdd - 1) - 1) % 1000000007)


from collections import Counter
(_, mod) = (input(), 10 ** 9 + 7)
c = Counter([int(i) % 2 for i in input().split()])
if c[1] == 0:
	c[1] = 1
print((pow(2, c[0] + c[1] - 1, mod) - 1) % mod)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


input()
lst = [int(j) for j in input().split(' ')]
first = True
res = 1
for j in lst:
	if not first or j % 2 == 0:
		res *= 2
	else:
		first = False
print((res - 1) % (10 ** 9 + 7))


def fast_power(a, b, P):
	if b == 0:
		return 1
	if b == 1:
		return a % P
	if b % 2 == 0:
		intermed = fast_power(a, b / 2, P)
		return intermed ** 2 % P
	else:
		intermed = fast_power(a, b - 1, P)
		return intermed * a % P
cnt = int(input().strip())
P = 10 ** 9 + 7
o = 0
e = 0
ip = [int(x) for x in input().strip().split(' ')]
assert cnt == len(ip)
for num in ip:
	if num % 2 == 0:
		e += 1
	else:
		o += 1
o -= 1
if o < 0:
	o = 0
print((fast_power(2, o + e, P) - 1) % P)


import math
import sys

def even_sum_subsets(numbers, modulo=int(1000000000.0 + 7)):
	size = len(numbers)
	odd = [n for n in numbers if n % 2]
	if odd:
		size -= 1
	return pow(2, size, modulo) - 1
size = int(sys.stdin.readline())
numbers = [int(x) for x in sys.stdin.readline().split()]
assert len(numbers) == size
print(even_sum_subsets(numbers))


n = int(input())
even = 0
odd = 0
modulo = 10 ** 9 + 7
nums = map(int, input().split())
for num in nums:
	if num % 2 == 0:
		even += 1
	else:
		odd += 1
if odd == 0:
	print((pow(2, n, modulo) + modulo - 1) % modulo)
else:
	print((pow(2, n - 1, modulo) + modulo - 1) % modulo)


n = int(input())
numbers = [int(x) for x in input().split()]
odd = 0
even = 0
for x in numbers:
	if x % 2 == 0:
		even += 1
	else:
		odd += 1
if odd == 0:
	print((2 ** n - 1) % 1000000007)
else:
	print((2 ** (n - 1) - 1) % 1000000007)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


from sys import stdin
N = stdin.readline()
Array = stdin.readline().split()
OddCount = 0
for a in Array:
	if int(a) % 2 == 1:
		OddCount += 1
OddSets = 0 if OddCount == 0 else 2 ** (OddCount - 1) - 1
EvenSets = 2 ** (int(N) - OddCount) - 1
NumberOfEvenSumSets = EvenSets if OddSets == 0 else EvenSets * OddSets + EvenSets + OddSets
print(NumberOfEvenSumSets % (10 ** 9 + 7))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


length = int(input())
nums = [int(n) for n in input().split(' ')]
mod = 10 ** 9 + 7
even = 0
odd = 0
for n in nums:
	if n % 2:
		odd += 1
	else:
		even += 1
if odd == 0:
	odd = 1
print((pow(2, even, mod) * pow(2, odd - 1, mod) - 1) % mod)


mod = 10 ** 9 + 7
n = int(input())
a = map(int, input().split())
ne = 0
no = 0
for ai in a:
	if ai & 1:
		no += 1
	else:
		ne += 1
if no > 0:
	no -= 1
n = pow(2, ne + no, mod) - 1
if n < 0:
	n += mod
print(n)


from math import factorial

def testRel():
	n = 13
	print(2 ** n)
	print(2 ** (n - 1))
	t = 0
	i = 1
	while i <= n:
		t += ck(n, i)
		i += 2
	print(t)

def ck(n, k):
	return int(factorial(n) / (factorial(n - k) * factorial(k)))

def calc(n):
	i = 2
	t = 0
	while i <= n:
		print(i, n)
		t += ck(n, i)
		i += 2
	print(n, t, '-->', 2 ** (n - 1))
	return t + 1
input()
S = [int(x) for x in input().split()]
nEven = len([x for x in S if x % 2 == 0])
nOdd = len(S) - nEven
if nOdd == 0:
	print((2 ** nEven - 1) % (10 ** 9 + 7))
else:
	print(2 ** nEven * 2 ** (nOdd - 1) % (10 ** 9 + 7) - 1)


t = int(input())
l = [int(i) for i in input().split()]
(p, q) = (0, 0)
for i in l:
	if i % 2 == 0:
		p += 1
	else:
		q += 1
if q != 0:
	(a, b) = ((pow(2, p) - 1) % 1000000007, (pow(2, q - 1) - 1) % 1000000007)
	temp = (a + b) % 1000000007 + a * b % 1000000007
	print(temp % 1000000007)
else:
	print((pow(2, p) - 1) % 1000000007)


def nchoosek(n):
	final = 0
	res = 1
	for i in range(1, n + 1):
		res = res * (n + 1 - i) // i
		if i % 2 == 0:
			final += res
	return final
MOD = 10 ** 9 + 7
N = int(input())
A = [int(x) for x in input().split()]
(odd, even) = (0, 0)
for i in range(N):
	if A[i] % 2 == 1:
		odd += 1
	else:
		even += 1
(odd_sum, even_sum) = (0, 0)
odd_sum = nchoosek(odd)
even_sum = pow(2, even) - 1
print((odd_sum + even_sum + odd_sum * even_sum) % MOD)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


n = int(input())
s = [int(x) for x in input().split()]
odds = 0
evens = 0
for i in s:
	if i % 2 == 0:
		evens += 1
	else:
		odds += 1
card_evens = 2 ** evens
card_odds = 1
if odds:
	card_odds = 2 ** (odds - 1)
num_combos = card_odds * card_evens - 1
print(num_combos % (10 ** 9 + 7))


mod = int(1000000000.0 + 7)
N = int(input())
a = [int(i) for i in input().split()]
n_evens = 0
n_odds = 0
for i in range(N):
	if a[i] % 2 == 0:
		n_evens += 1
	else:
		n_odds += 1
evens_subsets = 2 ** n_evens % mod
odds_subsets = 2 ** (n_odds - 1) % mod if n_odds > 0 else 1
result = (evens_subsets * odds_subsets - 1) % mod
print(result)


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


def even_subsets(L):
	even = 0
	odd = 0
	for i in L:
		if i % 2 == 0:
			even += 1
		else:
			odd += 1
	if odd == 0:
		return pow(2, even, 1000000007) - 1
	return pow(2, even + odd - 1, 1000000007) - 1
length = input()
L = input().split()
L = [int(i) for i in L]
print(even_subsets(L))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


mod = 1000000007
n = int(input())
A = list(map(int, input().split(' ')))
odd = len([x for x in A if x % 2 == 1])
even = n - odd
if odd == 0:
	odd = 1
print((2 ** (odd - 1) % mod * (2 ** even % mod) - 1) % mod)


def modPow(x, y, m):
	if y == 0:
		return 1
	if y == 1:
		return x
	temp = modPow(x, y // 2, m)
	if y % 2 == 0:
		return temp * temp % m
	else:
		return temp * temp % m * x % m
M = 10 ** 9 + 7
n = int(input())
lis = list(map(int, input().split()))
e = len(list(filter(lambda x: x % 2 == 0, lis)))
o = n - e
res = modPow(2, e, M)
if o > 0:
	res = res * modPow(2, o - 1, M) % M
print(res - 1)


N = int(input())
A = [int(ns) for ns in input().split()]
o = len([x for x in A if x % 2])
e = len(A) - o
if e:
	ee = 2 ** e
else:
	ee = 1
if o > 1:
	oo = 2 ** (o - 1)
else:
	oo = 1
M = 10 ** 9 + 7
print((ee * oo - 1) % M)


t = int(input())
MODULO = 1000000007

def PowMod(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = x * a % MODULO
		a = a * a % MODULO
		n >>= 1
	return x % MODULO
arr = list(map(int, input().split()))
(e, o) = (0, 0)
for i in arr:
	if i % 2 == 0:
		e += 1
	else:
		o += 1
ans = (PowMod(2, e) - 1 + MODULO) % MODULO
if o > 1:
	ans = ((ans + 1) * PowMod(2, o - 1) % MODULO - 1 + MODULO) % MODULO
print(ans)


N = int(input())
O = 0
for x in input().split():
	if int(x) % 2 == 1:
		O += 1
	E = N - O
if O > 1:
	P = 2 ** E * 2 ** O // 2 - 1
else:
	P = 2 ** E - 1
print(P % (10 ** 9 + 7))


mm = 1000000007

def fact(x):
	return dp[x]
n = int(input())
arr = list(map(int, input().split()))
e = 0
o = 0
for i in arr:
	if i % 2 == 0:
		e += 1
	else:
		o += 1
if o == 0:
	print(2 ** e - 1)
	exit(0)
ans = 2 ** (o - 1) * 2 ** e
ans -= 1
print(ans % mm)


n = int(input())
f = [int(x) for x in input().split()]
odd = 0
even = 0
for i in f:
	if i % 2:
		odd += 1
	else:
		even += 1
even = 2 ** even - 1
if odd > 0:
	odd = 2 ** (odd - 1) - 1
ans = (even + odd + even * odd) % (10 ** 9 + 7)
print(ans)


elements = int(input().strip())
mmod = 10 ** 9 + 7
(odds, evens) = (0, 0)
for elem in input().strip().split():
	if int(elem) % 2:
		odds += 1
	else:
		evens += 1
print((pow(2, evens, mmod) * pow(2, max(odds - 1, 0), mmod) - 1) % mmod)


__author__ = 'vikas'
n = int(input())
l = input()
l = list(map(int, l.split(' ')))
counte = 0
counto = 0
for i in l:
	if i % 2 == 0:
		counte = counte + 1
	else:
		counto = counto + 1
count = 0
x = (2 ** counte - 1) % 1000000007
y = 0
if counto:
	y = (2 ** (counto - 1) - 1) % 1000000007
count = count + x
count = count % 1000000007
count = count + y
count = count % 1000000007
count = count + x * y % 1000000007
count = count % 1000000007
print(int(count % 1000000007))


p = 1000000007
max_n = 100001
factorial = [1] * max_n
inv_factorial = [1] * max_n

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(g, y, x) = egcd(b % a, a)
	return (g, x - b // a * y, y)

def mod_inv(a, m):
	(gcd, x, y) = egcd(a, m)
	if gcd != 1:
		return None
	return x % m

def nCr(n, r):
	return factorial[n] * inv_factorial[r] * inv_factorial[n - r] % p
for i in range(1, max_n):
	factorial[i] = i * factorial[i - 1] % p
	inv_factorial[i] = mod_inv(i, p) * inv_factorial[i - 1] % p
n = int(input())
array = list(map(int, input().split()))
even = sum((num % 2 == 0 for num in array))
odd = n - even
print((pow(2, n, p) - 1 - pow(2, even, p) * sum((nCr(odd, i) for i in range(1, odd + 1, 2)))) % p)


from math import factorial
input()
numbers = [int(x) for x in input().split()]
even = 0
for x in numbers:
	if not x % 2:
		even += 1
odd = len(numbers) - even
x = 0.0
x = int(2 ** (odd - 1) - 1)
y = int(2 ** even - 1)
print((x + y + x * y) % (10 ** 9 + 7))


n = int(input())
arr = list(map(int, input().split()))
ev = 0
for i in arr:
	if i % 2 == 0:
		ev += 1
odd = n - ev
a = pow(2, ev, 1000000007)
a *= pow(2, max(0, odd - 1), 1000000007)
print((a - 1) % 1000000007)


T = int(input())
arr = input().split()
index = 0
for x in arr:
	arr[index] = int(x)
	index = index + 1
even_count = 0
odd_count = 0
for x in arr:
	if x % 2 == 0:
		even_count = even_count + 1
	else:
		odd_count = odd_count + 1
if even_count > 0:
	even_combs = pow(2, even_count) - 1
else:
	even_combs = 0
if odd_count > 0:
	odd_combs = pow(2, odd_count - 1) - 1
else:
	odd_combs = 0
total_combs = even_combs + odd_combs + even_combs * odd_combs
print('{}'.format(total_combs % 1000000007))


N = int(input())
odd = 0
for x in input().split(' '):
	odd += int(x) % 2
if odd > 1:
	print(pow(2, N - 1, 1000000007) - 1)
else:
	print(pow(2, N - odd, 1000000007) - 1)


N = int(input())
L = list(map(int, input().split()))
E = sum([1 for x in L if x % 2 == 0])
O = len(L) - E
if O > 0:
	print((2 ** E - 1 + 2 ** O // 2 - 1 + (2 ** E - 1) * (2 ** O // 2 - 1)) % (10 ** 9 + 7))
else:
	print(2 ** E - 1)


MOD = 1000000007

def main():
	num = int(input())
	arr = list(map(int, input().split()))
	evens = 0
	for i in arr:
		if i & 1 == 0:
			evens += 1
	e = 2 ** evens - 1
	if evens == num:
		print(e % MOD)
	else:
		o = 2 ** (num - evens - 1) - 1
		print((e + o + e * o) % MOD)
main()


input()

def pow_mod(x, y, z):
	if y < 0:
		return 1
	number = 1
	while y:
		if y & 1:
			number = number * x % z
		y >>= 1
		x = x * x % z
	return number
mod = 1000000007
l = list(map(int, input().split()))
ev = 0
od = 0
for i in l:
	if i % 2 == 0:
		ev += 1
	else:
		od += 1
print(pow_mod(2, ev, mod) * pow_mod(2, od - 1, mod) % mod - 1)


input()
nums = [int(x) for x in input().strip().split()]
evens = len([x for x in nums if x % 2 == 0])
odds = len(nums) - evens
even_subsets = 2 ** evens - 1
odd_subsets = 2 ** (odds - 1) - 1 if odds > 0 else 0
result = even_subsets + odd_subsets + even_subsets * odd_subsets
print(result % (10 ** 9 + 7))


n = int(input())
l = [int(x) for x in input().split()]
(e, o) = (0, 0)
for i in l:
	if i % 2 == 0:
		e += 1
	else:
		o += 1
if o == 0:
	o = 1
p = 1
for i in range(e + o - 1):
	p = p * 2 % 1000000007
print(p - 1)


mod = int(1000000000.0 + 7)
n = int(input())
od = 0
for x in map(int, input().split()):
	od += x & 1
ev = n - od
ans = pow(2, ev, mod)
fact = [1]
for i in range(100000):
	fact.append(fact[i] * (i + 1) % mod)
ans2 = 0
for x in range(0, od + 1, 2):
	ans2 = (ans2 + fact[od] * pow(fact[x], mod - 2, mod) % mod * pow(fact[od - x], mod - 2, mod)) % mod
ans = ans * ans2 % mod - 1
if ans < 0:
	ans += mod
print(ans)


_MOD = 10 ** 9 + 7

def get_number_of_subsets(nums):
	num_even = sum((num % 2 == 0 for num in nums))
	num_odd = sum((num % 2 != 0 for num in nums))
	even_combs = 2 ** num_even - 1
	odd_combs = 2 ** (num_odd - 1) - 1 if num_odd > 0 else 0
	return (even_combs + odd_combs + even_combs * odd_combs) % _MOD
_ = input()
numbers = [int(el) for el in input().split()]
print(get_number_of_subsets(numbers))


import math
a = int(input())
wholeArr = input().split(' ')
even = []
odd = []
i = 0
while i < a:
	if math.fmod(float(wholeArr[i]), 2) == 0:
		even.append(i)
	else:
		odd.append(i)
	i += 1
e = len(even)
o = len(odd)
formula = (2 ** e - 1) * 2 ** (o - 1) + (2 ** (o - 1) - 1)
mod = int(formula % 1000000007)
if wholeArr[0] == wholeArr[1]:
	print(2 ** a - 1)
else:
	print(mod)


n = int(input().strip())
arr = map(int, input().strip().split(' '))
modulo = 1000000007
fact = [1, 1]
for i in range(2, 100001):
	fact.append(i * fact[i - 1] % modulo)
even = 0
for a in arr:
	if a % 2 == 0:
		even += 1
odd = n - even
onlyEven = pow(2, even, modulo)
onlyOdd = 1
for i in range(odd // 2):
	delim = fact[2 * (i + 1)] * fact[odd - 2 * (i + 1)] % modulo
	onlyOdd = (onlyOdd + fact[odd] * pow(delim, modulo - 2, modulo) % modulo) % modulo
print(onlyEven * onlyOdd % modulo - 1)


input()
l = list(map(int, input().split()))
even = odd = 0
for i in l:
	if i % 2 == 0:
		even += 1
	else:
		odd += 1
EE = 2 ** even - 1
EO = 0
if odd > 0:
	EO = 2 ** (odd - 1) - 1
print((EE + EO + EE * EO) % 1000000007)


n = int(input())
ar = [int(x) % 2 for x in input().split(' ')]
evens = ar.count(0)
odds = ar.count(1)
print((2 ** (evens + max(odds - 1, 0)) - 1) % (10 ** 9 + 7))


n = int(input())
a = list(map(int, input().split()))
el = len(list(filter(lambda x: x % 2 == 0, a)))
ol = len(list(filter(lambda x: x % 2 != 0, a)))
X = 2 ** el - 1
Y = 0
if ol != 0:
	Y = 2 ** (ol - 1) - 1
tot = X + Y + X * Y
print(tot % (10 ** 9 + 7))


N = int(input())
args = input()
E = [int(x) for x in args.split()]

def power(k):
	if k == 0:
		return 1
	if k % 2 == 1:
		return 2 * (power(k // 2) % 1000000007) * (power(k // 2) % 1000000007) % 1000000007
	if k % 2 == 0:
		return power(k // 2) % 1000000007 * (power(k // 2) % 1000000007) % 1000000007

def check(arr):
	for i in range(N):
		if arr[i] % 2 == 1:
			return False
	return True
if check(E):
	print(power(N) - 1)
else:
	print(power(N - 1) - 1)


modulo = 10 ** 9 + 7

def twoPowerMod(n):
	twoThirtyMod = 73741817
	q = n // 30
	r = n % 30
	sum = 1
	for i in range(q):
		sum *= twoThirtyMod
		sum %= modulo
	sum *= 2 ** r
	sum %= modulo
	return sum
setSize = int(input().strip())
set = map(int, input().strip().split())
odds = 0
for i in set:
	if i % 2 == 1:
		odds += 1
evens = setSize - odds
result = twoPowerMod(evens)
if odds > 0:
	result *= twoPowerMod(odds - 1)
result -= 1
result %= modulo
print(result)


Q = 10 ** 9 + 7
import operator

def factorial_in_Q(i):
	if i == 0:
		return 1
	acc = 1
	for j in range(1, i + 1):
		acc = acc * j % Q
	return acc

def div_in_Q(a, b):
	return a * recip_in_Q(b) % Q

def recip_in_Q(a):
	return pow_in_Q(a, Q - 2)

def nCr_in_Q(n, r):
	if r > n:
		return 1
	return div_in_Q(factorial_in_Q(n), factorial_in_Q(r) * factorial_in_Q(n - r))

def pow_in_Q(a, n):
	acc = 1
	i = 0
	T = 2
	T_tt_i = 2 ** 0
	a_tt_T_tt_i = a % Q
	while n > 0:
		if n % (2 * T_tt_i):
			n -= n % (2 * T_tt_i)
			acc *= a_tt_T_tt_i
			acc %= Q
		i += 1
		T_tt_i *= 2
		a_tt_T_tt_i = a_tt_T_tt_i * a_tt_T_tt_i % Q
	return acc
_N = int(input())
As = list(map(int, input().split()))
assert _N == len(As)
Os = sum((i % 2 for i in As))
Es = _N - Os
E_ways = pow_in_Q(2, Es) - 1
O_ways = pow_in_Q(2, Os - 1) - 1
ways = 0
if Es:
	ways += E_ways
if Es and Os >= 2:
	ways += E_ways * O_ways
if Os >= 2:
	ways += O_ways
print(ways % Q)


from math import factorial
n = int(input())
ar = list(map(int, input().strip().split()))
ar_even = [x for x in ar if x % 2 == 0]
ar_odd = [x for x in ar if x % 2 == 1]
if len(ar_odd) > 0:
	print(int(2 ** len(ar_even) * 2 ** (len(ar_odd) - 1) - 1) % (10 ** 9 + 7))
else:
	print(int(2 ** len(ar_even) - 1) % (10 ** 9 + 7))


modo = 10 ** 9 + 7
tot = int(input().strip())
od = sum(map(lambda x: int(x) & 1, input().strip().split()))
print(pow(2, tot - (od != 0), modo) - 1)


mod = 10 ** 9 + 7
n = int(input())
l = [int(x) for x in input().split()]
n_even = 0
n_odd = 0
for x in l:
	if x % 2 == 0:
		n_even += 1
	else:
		n_odd += 1
p = 1
for i in range(n_even):
	p = 2 * p % mod
p -= 1
facts = [1]
for i in range(1, n_odd + 1):
	facts.append(facts[-1] * i % mod)
q = 0
for k in range(2, n_odd + 1, 2):
	a = facts[n_odd]
	b = facts[k]
	c = facts[n_odd - k]
	d = b * c % mod
	q = (q + a // d) % mod
p = 2 ** n_even - 1
q = max(0, 2 ** (n_odd - 1) - 1)
weird = (p + q + p % mod * (q % mod)) % mod
print(weird)


MOD_NUM = 10 ** 9 + 7
_ = input()
odd = 0
even = 0
for element in map(int, input().strip().split()):
	if element % 2:
		odd += 1
	else:
		even += 1
even_count = pow(2, even, MOD_NUM)
odd_count = pow(2, odd - 1, MOD_NUM) if odd > 1 else 1
print('{:.0f}'.format((even_count * odd_count - 1) % MOD_NUM))


n = int(input())
A = list(map(int, input().strip().split(' ')))
count_even = len([1 for a in A if a % 2 == 0])
count_odd = n - count_even
print((2 ** (count_even + max(count_odd - 1, 0)) - 1) % (10 ** 9 + 7))


def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	return int(input().strip())
MODULUS = 10 ** 9 + 7
N = read_int()
ai = read_ints()
ne = no = 0
for a in ai:
	if a % 2 == 0:
		ne += 1
	else:
		no += 1
es = pow(2, ne, MODULUS) - 1
if no > 0:
	os = pow(2, no - 1, MODULUS) - 1
else:
	os = 0
sol = (es + os + es * os) % MODULUS
print(sol)


N = int(input())
n = 0
m = 0
b = input()
a = b.split(' ')
for i in range(N):
	if int(a[i]) % 2 == 0:
		n = n + 1
	else:
		m = m + 1
mod = 1000000007
if m > 0:
	ans = (2 ** (N - 1) - 1) % mod
else:
	ans = 2 ** N - 1
print(ans)


MOD = 10 ** 9 + 7
n = int(input())
A = list(map(int, input().strip().split()))
assert len(A) == n
even = sum(map(lambda x: 1 if x % 2 == 0 else 0, A))
odd = n - even
even_subsets = pow(2, even, MOD)
if odd > 0:
	odd_subsets = pow(2, odd - 1, MOD)
else:
	odd_subsets = 1
print((even_subsets * odd_subsets - 1) % MOD)


length = int(input())
l = [int(x) for x in input().split()]
even = 0
for i in l:
	if i % 2 == 0:
		even += 1
odd = length - even
pure_even = 2 ** even - 1
if not odd == 0:
	pure_odd = 2 ** (odd - 1) - 1
	total = (pure_even + pure_odd + pure_even * pure_odd) % (10 ** 9 + 7)
	print(total)
else:
	print(pure_even)


import sys
n = int(input().strip())
v = [int(f) for f in input().strip().split()]
e = sum((1 for i in v if i % 2 == 0))
o = n - e
if o == 0:
	o = 1
s = pow(2, e) % 1000000007 * pow(2, o - 1) % 1000000007 - 1
print(s)


import sys
import math
A = [int(a) for a in list(sys.stdin)[1].split(' ')]
n_even = len([a for a in A if a % 2 == 0])
n_odd = len(A) - n_even
num_even_combos = 2 ** n_even
num_odd_combos = 2 ** max(n_odd - 1, 0)
print((num_even_combos * num_odd_combos - 1) % 1000000007)


P = 10 ** 9 + 7
N = int(input())
L = input().split()
S = {int(x) % 2 for x in L}
if S == {0}:
	print(pow(2, N, P) - 1)
else:
	print(pow(2, N - 1, P) - 1)


n = input()
lista = [int(i) for i in input().split()]
pares = [i for i in lista if i % 2 == 0]
impares = [i for i in lista if i % 2 != 0]
conjuntos_pares = 2 ** len(pares) - 1
conjuntos_impares = 2 ** (len(impares) - 1) - 1 if len(impares) > 0 else 0
print((conjuntos_pares + conjuntos_impares + conjuntos_pares * conjuntos_impares) % (10 ** 9 + 7))


N = int(input())
A = [int(x) for x in input().split(' ')]
(E, O) = (0, 0)
for i in range(N):
	if A[i] % 2 == 0:
		E += 1
	else:
		O += 1
if E > 0:
	Ecount = pow(2, E) - 1
else:
	Ecount = 0
if O > 0:
	Ocount = pow(2, O - 1) - 1
else:
	Ocount = 0
Total = (Ecount + Ocount + Ecount * Ocount) % 1000000007
print('%d ' % Total)


n = int(input())
A = [int(x) for x in input().split()]
odd = 0
even = 0
for a in A:
	if a % 2 == 0:
		even += 1
	else:
		odd += 1
x = 0
if even != 0:
	x = pow(2, even, 1000000007) - 1
y = 0
if odd > 1:
	y = pow(2, odd - 1, 1000000007) - 1
print((x + y + x * y) % 1000000007)


n = int(input())
arr = [int(x) for x in input().split()]
print((pow(2, n - 1 if any((x & 1 for x in arr)) else n, 10 ** 9 + 7) - 1) % (10 ** 9 + 7))


input()
a = list(map(int, input().split()))
if any((x % 2 for x in a)):
	q = pow(2, len(a) - 1, 10 ** 9 + 7)
else:
	q = pow(2, len(a), 10 ** 9 + 7)
print((q + 10 ** 9 + 6) % (10 ** 9 + 7))


n = int(input())
s = input()
m = 1000000007
no = s.split()
even = 0
odd = 0
for i in no:
	i = int(i)
	if i % 2 == 0:
		even += 1
	else:
		odd += 1
x = pow(2, even, m) - 1
if odd != 0:
	y = pow(2, odd - 1, m) - 1
else:
	y = 0
ans = x + y + x * y
print(ans % m)


import sys
N = int(sys.stdin.readline())
(odd, even) = (0, 0)
total = 0
for s in map(int, sys.stdin.readline().strip().split(' ')):
	if s % 2 == 0:
		even += 1
	else:
		odd += 1
print(str((2 ** even * (2 ** (odd - 1) if odd != 0 else 1) - 1) % (10 ** 9 + 7)))


N = int(input())
arr = list(map(int, input().split()))
even = [each for each in arr if each % 2 == 0]
odd = [each for each in arr if each % 2 != 0]
x = 2 ** int(len(even)) - 1
if len(odd) == 0:
	y = 0
else:
	y = 2 ** int(len(odd) - 1) - 1
print((x + y + x * y) % (10 ** 9 + 7))


n = int(input().strip())
nums = [int(x) for x in input().strip().split(' ')]
evens = 0
odds = 0
for i in nums:
	if i % 2 == 0:
		evens += 1
	else:
		odds += 1
odds = max(0, odds - 1)
print(((1 << evens + odds) - 1) % 1000000007)


print((lambda m, n: (pow(2, m - n, 1000000007) * pow(2, max(n - 1, 0), 1000000007) - 1) % 1000000007)(int(input()), sum(map(lambda x: x % 2, map(int, input().split())))))


import sys
MOD = 1000000007

def choose(n, k):
	if k < 0 or k > n:
		return 0
	else:
		(p, q) = (1, 1)
		for i in range(1, min(k, n - k) + 1):
			p *= n
			q *= i
			n -= 1
		return p // q
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
odds = sum((a % 2 for a in A))
evens = N - odds
n_evens = pow(2, evens, MOD) - 1
if odds == 0:
	print(n_evens)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_evens * n_odds + n_evens + n_odds) % MOD)


n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
odds = sum((i % 2 for i in a))
par = n - odds
n_par = pow(2, par, MOD) - 1
if odds == 0:
	print(n_par)
else:
	n_odds = pow(2, odds - 1, MOD) - 1
	print((n_par * n_odds + n_par + n_odds) % MOD)


def x(a):
	b = 1
	s = 1
	for i in range(1, a + 1):
		b = b * a // i
		if not i & 1:
			s += b % (10 ** 9 + 7)
		a -= 1
	return s % (10 ** 9 + 7)
input()
lst = [int(i) for i in input().split()]
(o, e) = (list(filter(lambda a: a & 1, lst)), list(filter(lambda a: not a & 1, lst)))
print((x(len(o)) * pow(2, len(e), 10 ** 9 + 7) - 1) % (10 ** 9 + 7))


P = 10 ** 9 + 7
N = int(input())
A = [int(j) for j in input().split()]
noodd = True
for i in A:
	if i % 2 == 1:
		noodd = False
		break
if noodd:
	print((2 ** N - 1) % P)
else:
	print((2 ** (N - 1) - 1) % P)


import sys
N = int(input())
l = [int(x.strip()) for x in input().split(' ')]
evens = 0
odds = 0
for i in range(N):
	if l[i] % 2 == 0:
		evens += 1
	else:
		odds += 1
if odds == 0:
	print((2 ** evens - 1) % (10 ** 9 + 7))
else:
	print((2 ** (odds - 1) * 2 ** evens - 1) % (10 ** 9 + 7))


from math import factorial
n = int(input())
nums = [int(i) for i in input().split(' ')]
evens = 0
odds = 0
for num in nums:
	if num % 2 == 0:
		evens += 1
	else:
		odds += 1
a = 2 ** evens - 1
if odds != 0:
	b = 2 ** (odds - 1) - 1
else:
	b = 0
modulo = 1000000007
answer = a + b + a * b
print(answer % modulo)


import resource, sys
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7
MAXN = 10 ** 6 + 15

def power(N, K):
	if K == 0:
		return 1
	elif K == 1:
		return N
	pw = power(N, K // 2)
	if K & 1:
		return pw * pw * N % MOD
	return pw * pw % MOD
fact = [1]
num = 1
for i in range(1, MAXN):
	num = num * i % MOD
	fact.append(num)

def comb(N, K):
	return fact[N] * power(fact[N - i] * fact[i] % MOD, MOD - 2) % MOD
N = int(input())
ar = list(map(int, input().split()))
odd = 0
even = 0
for item in ar:
	if item & 1:
		odd += 1
	else:
		even += 1
res = power(2, even)
s = 0
for i in range(0, odd + 1, 2):
	s = (s + comb(odd, i)) % MOD
print((res * s - 1 + MOD) % MOD)


n = int(input())
a = [int(item) for item in input().split()]
even = 0
if n == 1:
	print(1 - n % 2)
else:
	for i in range(n):
		if a[i] % 2 == 0:
			even += 1
	odd = n - even
	a = 2 ** even - 1
	if odd == 0:
		b = 0
	else:
		b = 2 ** (odd - 1) - 1
	print(int(a + b + a * b) % 1000000007)