Problem:
 Score : 200 points    Problem Statement We will say that two integer sequences of length N , x_1, x_2, ..., x_N and y_1, y_2, ..., y_N , are similar when |x_i - y_i| \leq 1 holds for all i ( 1 \leq i \leq N ).  In particular, any integer sequence is similar to itself.  You are given an integer N and an integer sequence of length N , A_1, A_2, ..., A_N .  How many integer sequences b_1, b_2, ..., b_N are there such that b_1, b_2, ..., b_N is similar to A and the product of all elements, b_1 b_2 ... b_N , is even?      Constraints  1 \leq N \leq 10  1 \leq A_i \leq 100         Input Input is given from Standard Input in the following format:  N  A_1  A_2  ...  A_N       Output Print the number of integer sequences that satisfy the condition.        Sample Input 1 2
2 3      Sample Output 1 7  There are seven integer sequences that satisfy the condition:   1, 2  1, 4  2, 2  2, 3  2, 4  3, 2  3, 4        Sample Input 2 3
3 3 3      Sample Output 2 26       Sample Input 3 1
100      Sample Output 3 1       Sample Input 4 10
90 52 56 71 44 8 13 30 57 84      Sample Output 4 58921

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

B = []

def createList(B,k):
    tmpB = []
    if k == 0:
        tmpB.append([A[k]-1])
        tmpB.append([A[k]])
        tmpB.append([A[k]+1])
    else:
        for b in B:
            b.append(A[k]-1)
            tmpB.append(b.copy())
            b.pop()
            b.append(A[k])
            tmpB.append(b.copy())
            b.pop()
            b.append(A[k]+1)
            tmpB.append(b.copy())
            b.pop()
    return tmpB

for n in range(N):
    B = createList(B,n)

count = 0
for b in B:
    for _ in b:
        if _ % 2 == 0:
            count += 1
            break

print(count)

Solution (Python):
N=int(input())
a=[]
a=input().split()
cnt=3**N
b=[]
for i in range(N):
    if int(a[i])%2==0:
        b.append(2)
    else:
        b.append(1)
ans=1
for i in range(N):
    ans*=b[i]
print(cnt-ans)

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
ans = 3 ** n

neg = 1
for a_i in a:
    if a_i % 2 == 0:
        neg *= 2

print(ans - neg)

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

def solve(num,ans,N,ite):
    count = 0
    ans.append(num)
    if len(ans) == N:
        a = 1
        for i in range(N):
            a *= ans[i]
        if a%2 == 0:
            return 1
        else:
            return 0
    for n in (-1,0,1):
        count += solve(x[ite+1]+n,ans[:],N,ite+1)
    return count
print(solve(x[0]-1,[],N,0)+solve(x[0],[],N,0)+solve(x[0]+1,[],N,0))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

ans = 3**n
odd = 1
for num in a:
    if num%2 == 0:
        odd = odd * 2

print(ans-odd)

Solution (Python):

N = int(raw_input())
A = map(int, raw_input().split(' '))


def rcount(array):
    if len(array) == 0:
        return 0
    top = array[0]
    length = len(array)

    base = 3**(length - 1)
    if top % 2:
        return 2 * base + rcount(array[1:])
    else:
        return base + 2 * rcount(array[1:])


print rcount(A)

Solution (Python):
N = int(input())
A = input().split()

ans = 0
kisu = 0
gusu = 0
for i in range(N):
    if int(A[i]) % 2 == 0:
        ans += 3**(N-i-1) * 2**(gusu)
        gusu += 1
    else:
        ans += 3**(N-i-1) * 2 * 2**(gusu)

print(ans)

Solution (Python):
n=int(input())
a=[int(i) for i in input().split()]
count=0

for i in range(n):
    if a[i]%2==0:
        count=count+1

print(3**n-2**count)

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

c = 1
for A in As:
    if (A % 2 == 0):
        c *= 2

print(3**N - c)

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

odd = 1
for a in A:
    if a%2 == 1:
        odd *= 1
    else:
        odd *= 2
print(3 ** len(A) - odd)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
num = 3**N
odd = sum([i%2 for i in A])
even = N - odd
print(num-(2**even))

Solution (Python):
N = int(input())
Astr = input().split()
A = []
for n in Astr:
    A.append(int(n))

count = 0
for n in A:
    if n%2==0:
        count += 1
        
print(3**N - 2**count)

Solution (Python):
N = int(input())
l = map(int , raw_input().split())

odd = 1

for i in l:
    if (i % 2 == 0):
        odd *= 2
    else:
        odd *= 1

print 3**N - odd

Solution (Python):
import functools


def main():
    n = int(input())
    A = [int(a) for a in input().split()]
    c = len([a for a in A if a%2 ==0])
    print(pow(3,n)-pow(2,c))

    
    
    
    
    
    


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
num_list = list(map(int, input().split()))
even = 0
for n in num_list:
    if n % 2 == 0:
        even += 1
print(3 ** N - 2 ** even)

Solution (Python):
def main():
  n = int(input())
  num = [int(x) for x in input().split()]
  odd = []
  for i in num:
    odd.append((i & 1)) 

  pre = [1]
  for i in range(len(odd)):
    if odd[i] == 1:
      pre.append(pre[-1] * 1)
    else:
      pre.append(pre[-1] * 2)

  ans = 0
  for i in range(len(odd)):
    if odd[i] == 0:
      cur = 1
    else:
      cur = 2

    ans += pre[i] * cur * (3 ** (n - i - 1)) 

  print(ans)



if __name__ == '__main__':
  main()

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

def rec(i, n):
    if i == N:
        return 1 if n % 2 == 0 else 0
    res = 0
    a = A[i]
    res += rec(i+1, n*(a-1))
    res += rec(i+1, n*(a+1))
    res += rec(i+1, n*a)

    return res

print(rec(0, 1))

Solution (Python):
from functools import reduce
N = int(input())
A = map(int, input().split())
a = map(lambda x: 1 if x%2 == 1 else 2,A)
print(3**N - reduce(lambda x,y:x*y,a))

Solution (Python):
N = int(input())
A = map(int, input().split(' '))
r = 0
for a_i in A:
    if a_i % 2 == 0:
        r += 1
print(3 ** N - 2 ** r)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
odd = [a % 2 for a in A]

print(3 ** N - 2 ** (N - sum(odd)))

Solution (Python):
n = int(raw_input())
a = map(int, raw_input().split())
ans = 1
for x in a:
    ans *= 2 - x % 2
print 3 ** n - ans

Solution (Python):


N = int(input())

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

dif = 1

for i in range(N):
    if(A[i] % 2 == 0):
        dif = dif * 2

print(pow(3, N) - dif)

Solution (Python):
n = int(input())
seki = 1
a = list(map(int, input().split()))
for i in range(n):
    if a[i] % 2 == 0:
        seki *= 2
print(3**n - seki)

Solution (Python):
N = int(input())						
a = [int(i) for i in input().split()]	

count_even = 0
for i in a:
	if i % 2 == 0:
		count_even += 1


ans = ( 3 ** N ) - ( 2 ** count_even )

print(ans)

Solution (Python):
n = int(input())
arr = map(int, input().split(" "))

pat = 3 ** n
odd = 1
for a in arr:
    if a % 2 == 0:
        odd *= 2

print(pat - odd)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

product = 1

for i in a:
    if i % 2 == 0:
        product *= 2
    else:
        product *= 1

print(3**len(a) - product)

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())   
even = 0
odd = 1
for ai in A:
    if ai % 2 == 0:
        even = 3*even + odd
        odd = 2*odd
    else:
        even = 3*even + 2*odd
        odd = odd
print even

Solution (Python):
def calc(n, ls):
    if n == 1 and ls[0]%2==0:
        return 1
    cnt = 1
    for item in ls:
        if item%2 == 0:
            cnt *= 2
        else:
            cnt *= 1
    return 3 ** n - cnt

n = int(input())
ls = list(map(int, input().split()))
print(calc(n, ls))

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]

cnt = 0
for i in range(n):
    if a[i] % 2 == 0:
        cnt += 1

x = 3 ** n - 2 ** cnt

print(x)

Solution (Python):
N = int(input())
a = map(int, input().split())
tmp = 3 ** N
g = len([c for c in a if c % 2 == 0])
print(tmp - (2 ** g))

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
n=i1()
a=i2()
b=1
for i in range(n):
 if a[i]%2==0:
    b*=2
print(3**n-b)

Solution (Python):
def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    bn = 3 ** N
    odd = 1
    for i in A:
        if not i % 2:
            odd *= 2

    print(bn - odd)

main()

Solution (Python):
def get_result(A):
    res = 1
    total = 3 ** len(A)
    for i, ai in enumerate(A):
        res *= 2 if ai % 2 == 0 else 1
    return total - res
n = input()
A = [int(ai) for ai in input().split()]
print(get_result(A))

Solution (Python):
n = int(input())
c = 0
for a in map(int, input().split()):
    c += a & 1 == 0
print(3 ** n - 2 ** c)

Solution (Python):



n = raw_input()
n = int(n)

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

gnum = 0
for i in range(n):
    if a[i]%2 == 0:
        gnum += 1

ans = 3**n - 2**gnum

print ans

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

ans = 1

for i in range(N):
    ans = ans*3

even = 0
for i in a:
    if i%2==0:
        even += 1

miss = 1
for i in range(even):
    miss = miss*2

print(ans-miss)

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

for i in range(N):
    if A[i]%2 == 0:
        m *= 2

print(3**N - m)

Solution (Python):
N = int(input())
As = list(map(int, input().split()))
ret = 3**N
tmp = 1
for a in As:
    if a % 2 == 0:
        tmp *= 2
print(ret-tmp)

Solution (Python):
import operator,functools
print(3**(int(input())) - functools.reduce(operator.mul, map(lambda x: 2-(int(x)%2),input().split()), 1))

Solution (Python):
N = int(input())
a = map(int,input().split())
count = 1
temp = 1

for i in a:
	temp *= 3
	if i%2 == 1:
		count *= 1
	else :
		count *= 2
print(temp - count)

Solution (Python):




"""
Created on Mon Oct  9 22:12:40 2017

@author: kitagenbakurou
"""
import numpy as np
import copy

N = input()
N = int(N)
s = input().split()
s = [int(i) for i in s]

cnt = 1
for i in range(N) : 
    if s[i] % 2 == 0 : cnt *= 2
    else : cnt *= 1

print(3 ** N - cnt)

Solution (Python):
n = int(input())
a_list = input().split()
a_list = [int(x) for x in a_list]

zentori = 3**n

a_list_2 = [x%2 for x in a_list]
from collections import Counter

counter = Counter(a_list_2)

bad_tori = (2**counter[0])

print(zentori-bad_tori)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
M = 3 ** N
odd_num = 1
for i in range(N):
    if A[i] % 2 == 0:
        odd_num = odd_num * 2
print(M - odd_num)

Solution (Python):


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

even = 0

for i in a:
    if(i%2==0):
        even += 1

print(3**len(a)-2**even)

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

whole = 3**N
even = 0
for i in range(N):
    if src[i]%2 == 0: even += 1

print(whole - 2**even)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))

odds = 1
for i in range(n) :
    if a[i]%2 == 0 :
        odds *= 2
else :
    print(3**n-odds)

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

def func(l,b):
	if len(l) == 1:
		if(b):
			return 3
		else:
			return 1 + (l[0] % 2)
	if(b):
		return 3 * func(l[1:], b)
	else:
		if l[0] % 2 == 0:
			return 2*func(l[1:], False) + func(l[1:], True)
		else:
			return 2*func(l[1:], True) + func(l[1:], False)
print(func(A,False))

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
odd_cand = 1
ans = 1
for i in A:
    if i%2==0:
        odd_cand *= 2
    ans *= 3

print(ans - odd_cand)

Solution (Python):
n = input()
l = list(map(int,input().split()))

al = 1
od = 1

al = al * (3 ** int(n))

for i in l:
    if i %2 == 0:
        od = od *2
        
print(al-od)

Solution (Python):
N = int(raw_input())
A = map(int, raw_input().split())
ans = 1
for i in range(N):
    if A[i] % 2 == 0:
        ans *= 2
    else:
        ans *= 1
print 3**N - ans

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
k = 1
for i in a:
	if i%2 == 0:
		k *= 2
print(3**n-k)

Solution (Python):
N = int(input())
A = [int(x) for x in input().split()]
ret = 0
for state in range(1 << N):
    flag = False
    ans = 1
    for i in range(N):
        if (state >> i & 1):
            if A[i] % 2 == 1:
                flag = True
            ans *= 2
        else:
            if A[i] % 2 == 0:
                flag = True
    if flag:
        ret += ans
print(ret)

Solution (Python):



N = int(input())

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

count = 1

for i in A:
	if i % 2 == 0:
		count *= 2
	else:
		pass

ans = (3 ** len(A)) - count

print(ans)

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

cnt = 0
for i in range(N):
    if A[i] % 2 == 0:
        cnt+= 1
        
x = 3**N - 2 **cnt
print(x)

Solution (Python):
n = int(raw_input())
a = map(int,raw_input().split(" "))

ans = pow(3,n)
x = 1
for z in a:
  if z%2 == 0:
    x = x * 2

print ans - x

Solution (Python):

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

cnt = 1

for ai in a:
    if ai%2== 0:
        cnt*=2
print(3**n - cnt)

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

all = 3 ** N

odd = 1 if A[0] % 2 == 1 else 2
for n in range(N-1):
    odd *= 1 if A[n+1] % 2 == 1 else 2

print(all-odd)

Solution (Python):

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

for a in A:
    if a % 2 == 0:
        cnt += 1

print(3**N - 2**cnt)

Solution (Python):

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

all_count = pow(3, N)
odd_count = 1
for i in range(N):
    if A_list[i] % 2 == 0:
        odd_count *= 2

print(all_count - odd_count)

Solution (Python):
n=int(raw_input())
inp=raw_input().split(" ")
count=0
for an in inp:
 count+=((int(an)-1)%2)
print pow(3,n)-pow(2,count)

Solution (Python):
n=int(input())
a=input().split(' ')
m=0
for i in range(n):
  if int(a[i]) % 2 == 0:
    m+=1
print(3**n-2**m)

Solution (Python):
import sys

N = int(sys.stdin.readline())
As = list(map(int, sys.stdin.readline().split()))
res = 1
for A in As:
    if A % 2 == 0:
        res *= 2
print(3**len(As) - res)

Solution (Python):
n = int(input())

A = list(map(int, raw_input().split()))

(dp0, dp1) = (1, 0)
for x in A:
    (ndp0, ndp1) = (0, 0)
    for y in range(x - 1, x + 2):
        if y % 2 == 0:
            ndp1 += dp0
            ndp1 += dp1
        else:
            ndp0 += dp0
            ndp1 += dp1
    (dp0, dp1) = (ndp0, ndp1)
print dp1

Solution (Python):
import sys
n = input()
a = [int(i) for i in raw_input().split()]

ans = 3**n

minus = 1
for i in a:
    if i % 2 == 0:
        minus *= 2

print ans - minus

Solution (Python):



def rl(s): return xrange(len(s))

import sys
stdin = sys.stdin
def tokens(): return stdin.readline().strip().split()
def ints(): return map(int, tokens())
def int1(): return int( stdin.readline().strip() )

INF = 2147483647



N = int1()

aa = ints()

total = 3**N
odds = 1
for a in aa:
    if a & 1 == 0:
        odds *= 2

print total - odds

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
ans = 3**n
odd = 1
for ai in a:
    if ai % 2 == 0:
        odd *= 2
ans -= odd
print(ans)

Solution (Python):
n = int(input())

a = [int(t) for t in input().split()]


ans = 3**n

x = 1
for i in range(n):
    if a[i]%2 == 0:
        x *= 2

print(ans - x)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    b = c = 0
    for d in a:
        if d%2 == 0:
            b += 1
        else:
            c += 1
    t = 3**n

    return t - (2**b)


print(main())

Solution (Python):
N = input()
A = map(int,raw_input().split(" "))

r = 1

for i in range(N):
    if A[i]%2 == 0:
        r *= 2

print 3 ** N  - r

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

all = 3 ** N
no = 1
for a in A:
    no *= 2 if a % 2 == 0 else 1
print(all - no)

Solution (Python):
import numpy as np
import math as mt

n = int(input())
arr = [int(x) for x in input().split(' ')]
sum = 1
for x in arr:
    if x % 2 == 0:
        sum *= 2
    else:
        sum *= 1
print(int(mt.pow(3,n) - sum))

Solution (Python):


import math
import fractions
import heapq
import collections
import re
import array
import bisect

from collections import Counter, defaultdict


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]


def main():
    N = int(input())
    ans = 3**N
    ad = 1
    for i in map(int, input().split()):
        if i % 2 == 0:
            ad *= 2
    return ans - ad


if __name__ == "__main__":
    print(main())

Solution (Python):
n = int(input())
*A, = map(int, input().split())

from itertools import product

ans = 0
for P in product(range(3), repeat=n):
    even = 0
    for i in range(n):
        b = A[i] + P[i] - 1
        even |= (b % 2) == 0
    if even:
        ans += 1
print(ans)

Solution (Python):
n = int(input())
A = list(map(int,input().split()))
ans = 1
odd = 1
for i in range(0,n):
    ans *= 3
    if A[i]%2 == 0:
        odd *= 2
print(ans-odd)

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
c = [0] * 2
for i in a:
	c[i % 2] += 1
print(3 ** n - 2 ** c[0])

Solution (Python):
n = int(input())
xs = [int(x) for x in input().split()]
whole = 3 ** n
ex = 1
for x in xs:
    if x % 2 == 0:
        ex *= 2
print(whole - ex)

Solution (Python):
input()
a = 1
b = 1
for x in map(int, raw_input().split()):
    a *= 3
    if x % 2 == 0:
        b *= 2
print a - b

Solution (Python):
from itertools import product

N = int(raw_input())
A = map(int, raw_input().split())
ans = 0

for p in product((-1, 0, 1), repeat=N):
    B = A[:]
    for i in xrange(N):
        B[i] += p[i]
    if sum(b % 2 == 0 for b in B) > 0:
        ans += 1

print ans

Solution (Python):



import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

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

odd = 1
for a in A:
    if a % 2 == 0:
        odd *= 2
print(3 ** N - odd)

Solution (Python):
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

print(3**N - 2**even)

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


all_odd = 1
for a in A:
    if a%2 ==0:
        all_odd*=2

print(3**N - all_odd)

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

odd = 1
for a in A:
    if a % 2 == 0:
        odd = odd*2
        
print(3**N-odd)

Solution (Python):
n = int(input())
ret = 1
a = list(map(int,input().split()))
for i in a:
    if i%2==0:
        ret *= 2

print(3**n-ret)

Solution (Python):
N = input()
A = map(int, raw_input().split())
x = 1
for a in A:
    if a%2==0:
        x *= 2
print 3**N - x

Solution (Python):

n = int(input())
a = list(map(int, input().split()))
k = 1
for a_i in a:
    if a_i % 2 == 0:
        k *= 2
print(3 ** n - k)

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

z = 1
for i in a:
	c = 0
	for j in range(i - 1, i + 2):
		if j % 2 == 1:
			c += 1
	z *= c

print 3 ** n - z