Problem:
 Score : 200 points    Problem Statement There are N bags of biscuits. The i -th bag contains A_i biscuits.  Takaki will select some of these bags and eat all of the biscuits inside.
Here, it is also possible to select all or none of the bags.  He would like to select bags so that the total number of biscuits inside is congruent to P modulo 2 .
How many such ways to select bags there are?      Constraints  1 \leq N \leq 50  P = 0 or 1  1 \leq A_i \leq 100         Input Input is given from Standard Input in the following format:  N  P  A_1  A_2 ... A_N       Output Print the number of ways to select bags so that the total number of biscuits inside is congruent to P modulo 2 .        Sample Input 1 2 0
1 3      Sample Output 1 2  There are two ways to select bags so that the total number of biscuits inside is congruent to 0 modulo 2 :   Select neither bag. The total number of biscuits is 0 .  Select both bags. The total number of biscuits is 4 .        Sample Input 2 1 1
50      Sample Output 2 0       Sample Input 3 3 0
1 1 1      Sample Output 3 4  Two bags are distinguished even if they contain the same number of biscuits.       Sample Input 4 45 1
17 55 85 55 74 20 90 67 40 70 39 89 91 50 16 24 14 43 24 66 25 9 89 71 41 16 53 13 61 15 85 72 62 67 42 26 36 66 4 87 59 91 4 25 26      Sample Output 4 17592186044416

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]
n,p = m()

a = l()

on= 0

su = 0

for i in range(n):
    a[i] %= 2
    if a[i] == 1:
        on += 1
no = n - on

if p % 2 == 0:
    if on % 2 == 0:
        for i in range(0,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu
    else:
        for i in range(1,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

else:
    if on % 2 == 0:
        for i in range(1,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

    else:
        for i in range(0,on+1,2):
            su += cmb(on,i)
        suu = 0
        for i in range(no+1):
            suu += cmb(no,i)
        su *= suu

print(su)

Solution (Python):
from scipy import misc
N,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
o = sum(x % 2 == 1 for x in A)
e = sum(x % 2 == 0 for x in A)
if P == 0:
    sum0 = sum(misc.comb(o, i, exact=True) for i in range(0, o+1, 2))
    print(sum0*(2**e))
else:
    sum1 = sum(misc.comb(o, i, exact=True) for i in range(1, o+1, 2))
    print(sum1*(2**e))

Solution (Python):
def comb(n, r):
    x, y = 1, 1
    for i in range(n, n - r, -1):
        x *= i
        y *= i + r - n
    return x / y

n, p = map(int, input().split())
a = list(map(int, input().split()))
m = 0
for i in a:
    if i % 2 == 0:
        m += 1
x = 0
for i in range(1, n - m + 1, 2):
    x += comb(n - m, min(i, n - m - i))
x *= 2 ** m
print(int(x) if p == 1 else int(2 ** n - x))

Solution (Python):
n,p = map(int,input().split())
a = [int(i) for i in input().split()]
odd = 0
evil = 0
for i in a:
    if i % 2== 0:
        evil += 1
    else:
        odd += 1
if p==1 and odd ==0:
    print(0)
elif evil ==n:
    print(pow(2,n))
else:
    print(pow(2,n-1))

Solution (Python):
from scipy.misc import comb

N,P=map(int,input().split())
A=list(map(int,input().split()))
e,o = 0,0

for i in A:
    if i%2==0:
        e +=1
    else:
        o +=1

       
if P==0:
    e_x = 2**e
    o_x = 0
    for j in range(0,o+1,2):
        
        o_x += comb(o,j,exact=True)
else:
    e_x = 2**e
    if o==0:
        o_x = 0
    else:
        o_x = 0
        for j in range(1,o+1,2):
            
            o_x += comb(o,j,exact=True)

ans = e_x * o_x
print(ans)

Solution (Python):
from operator import mul
from functools import reduce

n, p = map(int, input().split())

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

a_0 = []
a_1 = []
for j in a_list:
    if j % 2 == 0:
        a_0.append(j)
    else:
        a_1.append(j)

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


if p == 0:
    ans = 1

    tmp_2 = 0
    if len(a_0) >= 1:
        for i in range(1,len(a_0)+1):
            tmp_2 += combinations_count(len(a_0), i)
    
    ans += tmp_2
    
    tmp_1 = 0
    if len(a_1) > 2:
        for i in range(2,len(a_1)+1, 2):
            
            tmp_1 += combinations_count(len(a_1), i)
    elif len(a_1) == 2:
        tmp_1 += 1
    ans += tmp_1
    

    ans += tmp_1*tmp_2


elif p == 1:
    ans = 0

    tmp_2 = 1
    if len(a_0) >= 1:
        for i in range(1,len(a_0)+1):
            tmp_2 += combinations_count(len(a_0), i)
    

    if len(a_1) >= 1:
        for i in range(1,len(a_1)+1, 2):
            
            tmp = combinations_count(len(a_1), i)
            ans += tmp*tmp_2

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, p = map(int, readline().split())
a = list(map(int, readline().split()))
cnt_1 = 0
cnt_2 = 0
for i in a:
    if i % 2 == 1:
        cnt_1 += 1
    else:
        cnt_2 += 1
ans = 2 ** max(0, cnt_1 - 1) * 2 ** cnt_2
if p == 1 and cnt_1 == 0:
    ans = 0
print(ans)

Solution (Python):
n, p = map(int, input().split())
l = list(map(int, input().split()))
a = []
for i in l:
    a.append(i % 2)
    
if p == 0:
    if a.count(1) == 0:
        print(2 ** n)
    
    else:
        print(2 ** (n - 1))
        
else:
    if a.count(1) == 0:
        print(0)
    
    else:
        print(2 **(n - 1))

Solution (Python):
from math import factorial

def combi(n, k):
  return factorial(n) // factorial(n-k) // factorial(k)

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
for i in range(P, o+1, 2):
  ans += combi(o, i)
print(ans * pow(2, e))

Solution (Python):
from scipy.misc import comb
from math import factorial

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
if P == 0:
  for i in range(0, o+1, 2):
    ans += comb(o, i, exact=True)
  print(ans * pow(2, e))
else:
  for i in range(1, o+1, 2):
    ans += comb(o, i, exact=True)
  print(ans * pow(2, e))

Solution (Python):
from math import factorial

def combi(n, k):
  return factorial(n) // factorial(n-k) // factorial(k)

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

e = len([a for a in A if a % 2 == 0])
o = N - e

ans = 0
if P == 0:
  for i in range(0, o+1, 2):
    ans += combi(o, i)
  print(ans * pow(2, e))
else:
  for i in range(1, o+1, 2):
    ans += combi(o, i)
  print(ans * pow(2, e))

Solution (Python):

def inputlist(): return [int(j) for j in input().split()]


N,P = inputlist()
A = inputlist()
for i in range(N):
    A[i] = A[i] % 2
from collections import Counter
c = Counter(A)
n0 = c[0]
n1 = c[1]
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
ans2 = 0
for i in range(1,n1+1):
    if i % 2 == 0:
        continue
    ans += comb(n1,i)
for i in range(n1+1):
    if i % 2 == 1:
        continue
    ans2 += comb(n1,i)
if P == 1:
    print((2**n0)*ans)
if P == 0:
    print((2**n0)*ans2)

Solution (Python):
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def print_list(l): print(*l, sep='\n')
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def No(): print('No')

def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime

N,P = imn()
A = iln()

contains_odd_number = False
for a in A:
    if a % 2 == 1:
        contains_odd_number = True
if contains_odd_number:
    print(2**(N-1))
else:
    if P == 0:
        print(2**N)
    else:
        print(0)

Solution (Python):
N, P = map(int, input().split())
biscuits = list(map(int, input().split()))
gu = 0
ki = 0
for i in range(N):
    if biscuits[i] % 2 == 0:
        gu += 1
    else:
        ki += 1
if P == 1 and ki == 0:
    print(0)
elif gu == N:
    print(pow(2,N))
else:
    print(pow(2,N-1))

Solution (Python):
from math import factorial
def combi(n,k):
    return factorial(n) // factorial(k) // factorial(n-k)

n,p = map(int,input().split())
a = list(map(int,input().split()))
even = 0
odd  = 0
for i in a:
    if i&1:
        odd  += 1
    else:
        even += 1
picke = 0
for i in range(even + 1):
    picke += combi(even,i)
picko = 0
for i in range(p,odd + 1,2):
    picko += combi(odd,i)
print(picke*picko)

Solution (Python):
N, P = map(int, input().split())
A = list(map(int, input().split()))
mod0, mod1 = 0, 0
for a in A:
  if a % 2 == 0: mod0 += 1
  else: mod1 += 1


from math import factorial
comb0 = 2 ** mod0
comb1 = 0
if mod1 > 0:
  for i in range(P, mod1+1, 2):
    comb1 += factorial(mod1) // (factorial(mod1 - i) * factorial(i))
else:
  if P == 0:
    comb1 = 1
ans = comb0 * comb1

print(ans)

Solution (Python):



N, P = map(int, input().split())
a_list = list(map(int, input().split()))


even_count = 0
odd_count = 0


for a in a_list:
    if a%2==0:
        even_count += 1
    else:
        odd_count = 2 ** (N - 1)
if even_count==len(a_list):
    if P==0:
        print(2 ** N)
    else:
        print(0)
else:
    print(2**(N-1))

Solution (Python):
def comb(n, k):
    if n - k < k:
        k = n - k
    if k == 0:
        return 1
    a = 1
    b = 1
    for i in range(k):
        a *= n - i
        b *= i + 1
    return a // b


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

odds = sum(a % 2 for a in A)
evens = len(A) - odds

print(sum(comb(odds, i) for i in range(P, odds + 1, 2)) * (2 ** evens))

Solution (Python):
def main():
    from math import factorial

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

    b = [i % 2 == 0 for i in a]
    n, m = b.count(True), b.count(False)
    c = factorial(m)

    x = 2 ** n
    y = sum([c // factorial(i) // factorial(m - i) for i in range(0, m + 1, 2)])
    z = sum([c // factorial(i) // factorial(m - i) for i in range(1, m + 1, 2)])

    if p == 0:
        print(x * y)
    else:
        print(x * z)


if __name__ == '__main__':
    main()

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

A = list(map(int, input().split()))
B = []
for i in A:
    B.append(i%2)

zero = B.count(0)
one = B.count(1)

t = 0

from operator import mul
from functools import reduce

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

for i in range(1, one+1, 2):
    t += combinations_count(one, i)

if p == 1:
    print(t * 2**zero)
else:
    print(2**n - t * 2**zero)

Solution (Python):
from operator import mul
from functools import reduce

N, P = map(int, input().split())
A = list(map(int, input().split()))
cE, cO = 0, 0

for a in A:
    if a % 2 == 0:
        cE += 1
    else:
        cO += 1



if cO == 0:
    ans = 2 ** N if P == 0 else 0
    print(ans)
else:
    
    
    
    
    
    
    
    
    print(2 ** (N - 1))

Solution (Python):

import math
n,p = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0,0] for _ in range(n)]
if a[0] & 1:
    dp[0][0] = 1
    dp[0][1] = 1
else:
    dp[0][0] = 2
    dp[0][1] = 0
for i in range(1,n):
    if a[i] & 1:
        dp[i][0] = dp[i-1][0]+dp[i-1][1]
        dp[i][1] = dp[i-1][0]+dp[i-1][1]
    else:
        dp[i][0] = dp[i-1][0]*2
        dp[i][1] = dp[i-1][1]*2
print(dp[n-1][p])

Solution (Python):

import sys
def comb(n, k):
    k = min(n-k,k)
    ans = 1
    for i in range(1, k + 1):
        ans = (ans * (n + 1 - i) // i)
    return ans

def solve(N: int, P: int, A: "List[int]"):
    odd = 0
    even = 0

    for i in range(N):
        if A[i]&1:
            odd += 1
        else:
            even += 1
    
    all_pattern = 2**N
    odd_pattern = 0
    for o in range(1,odd+1):
        if o&1:
            odd_pattern += comb(odd,o)
    odd_pattern *= 2**even

    if P:
        print(odd_pattern)
    else:
        print(all_pattern-odd_pattern)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, P, A)

if __name__ == '__main__':
    main()

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

o, e = 0, 0
for i in a:
    if i % 2 == 0:
        e += 1
    else:
        o += 1

def comb(n, r):
    ret = 1
    for i in range(r):
        ret *= n - i
        ret //= i + 1
    return ret

res = 0 
if p == 0:
    for i in range(0, o + 1, 2):
        res += comb(o, i)
else:
    for i in range(1, o + 1, 2):
        res += comb(o, i)
res *= 2 ** e
print(res)

Solution (Python):
def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 1 and count[1] == 0:
        print(0)
    elif count[1] == 0:
        print(pow(2, bags))
    else:
        print(n_pow(2, bags - 1))


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import sys
import heapq
from collections import Counter
from collections import deque
from fractions import gcd
from functools import reduce
from math import factorial

sys.setrecursionlimit(4100000)
from functools import lru_cache

INF = 1 << 60
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, p = map(int, input().split())
is_all_even = True
a = [0] * n
a = list(map(int, input().split()))
for i in a:
    if i % 2 == 1:
        is_all_even = False
        break
ans = 0
if is_all_even:
    if p == 0:
        ans = 2 ** n
    else:
        ans = 0
else:
    ans = 2 ** (n - 1)
print(ans)

Solution (Python):
N, P = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (N + 1) for i in range(2)]
dp[0][0] = 1
for i in range(N):
    if A[i] % 2 == 0:
        
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]
        
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]
    else:
        
        dp[0][i + 1] += dp[1][i]
        dp[1][i + 1] += dp[0][i]
        
        dp[0][i + 1] += dp[0][i]
        dp[1][i + 1] += dp[1][i]


print(dp[P][N])

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

dp = [[0] * 2 for _ in range(n + 1)]
dp[0][0] = 1

for i, e in enumerate(a, 1):
    for j in range(2):
        r = e % 2
        dp[i][j] = dp[i-1][j] + dp[i-1][(j-r)%2]

print(dp[n][p])

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

dp = [[0] * 2 for _ in range(n + 1)]
dp[0][0] = 1

for i, e in enumerate(a, 1):
    if e % 2:
        dp[i][0] = dp[i-1][0] + dp[i-1][1]
        dp[i][1] = dp[i-1][1] + dp[i-1][0]
    else:
        dp[i][0] = dp[i-1][0] * 2
        dp[i][1] = dp[i-1][1] * 2

print(dp[n][p])

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    if all(a == 0 for a in A):
        print(2**N if P == 0 else 0)
    else:
        print(2**(c[1]-1) * 2**c[0])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    if all(a == 0 for a in A):
        print(2**N if P == 0 else 0)
    else:
        print(2**(c[1]-1) * 2**c[0])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = (int(i) for i in input().split())
    A = [int(i) % 2 for i in input().split()]
    from collections import Counter
    c = Counter(A)
    ans = 0
    if P == 0:
        ans = 2**c[0]
        if c[1]:
            ans *= 2**(c[1]-1)
    else:
        if c[1]:
            ans = 2**(c[1]-1)
        ans *= 2**c[0]
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


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

odd = sum([a % 2 for a in A])
even = len(A) - odd

if odd == 0 and P == 1:
    print(0)
elif odd == 0 and P == 0:
    print(2 ** even)
else:
    ans = (2 ** even) * (2 ** (odd - 1))
    print(ans)

Solution (Python):
N,P = map(int, input().split())
A = [int(a) for a in input().split()]

even = 0
odd = 0
for a in A:
    if a%2 == 0:
        even += 1
    else:
        odd += 1

if odd == 0:
    if P == 0:
        ans = pow(2, N)
    else:
        ans = 0
else:
    ans = pow(2, N-1)

print(ans)

Solution (Python):
N,P = map(int, input().split())
A = [int(a) for a in input().split()]

even = 0
odd = 0
for a in A:
    if a%2 == 0:
        even += 1
    else:
        odd += 1

L = [1]*(N+1)
for i in range(N):
    L[i+1] = L[i]*(i+1)
    
def cmb(n, r):
    return L[n]//L[r]//L[n-r]

ans = pow(2, N)    
for i in range(1, odd+1, 2):
    ans -= cmb(odd, i)*pow(2, even)
if P == 1:
    ans = pow(2, N) - ans

print(ans)

Solution (Python):
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N,P = map(int, input().split())
A = [int(i) for i in input().split()]

odd,even = 0,0
for a in A:
    if a % 2 == 0: even += 1
    else: odd += 1

ans = 0
for o in range(1 if P % 2 == 1 else 0, odd + 1, 2):
    for e in range(even + 1):
        ans += comb(odd, max(0,o)) * comb(even, e)

print(ans)

Solution (Python):
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N,P=map(int,input().split())
A=list(map(int,input().split()))
odd=len([i for i in A if i%2==1])
even=len([i for i in A if i%2==0])

if P==0:
    ans=2**even
    ans_odd=1
    if odd!=0:
        ans_odd=0
        for i in range(odd//2+1):
            ans_odd+=cmb(odd,2*i)
else:
    ans=2**even
    ans_odd=0
    if odd!=0:
        for i in range(odd//2):
            ans_odd+=cmb(odd,2*i+1)
print(ans*ans_odd)

Solution (Python):
N, P = map(int, input().split())
A_li = list(map(int, input().split()))
for i, a in enumerate(A_li) :
    if a % 2 == 1 :
        break
    if i == N - 1 :
        if P == 0 : 
            print(2 ** N)
        else :
            print(0)
        exit()
print(2 ** (N - 1))

Solution (Python):
n,p = map(int,input().split())
a = list(map(int, input().split()))
if all(x%2 == 0 for x in a):
    if p == 0:
        ans = 2**n
    else:
        ans = 0
else:
    ans = 2**(n-1)
print (ans)

Solution (Python):
import math

def comb(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

for i in range(n):
  a[i] = a[i]%2

for i in range((a.count(1)+1)//2):
  res = res + comb(a.count(1), 2*i+1)
if res == 0 and p == 0:
  res = 1
res = res * 2**a.count(0)
print(res)

Solution (Python):
n, p = map(int, input().split())
a = list(map(int, input().split()))
a_even = 0
a_odd = 0
for i in a:
    if i % 2 == 0:
        a_even += 1
    else:
        a_odd += 1
        
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k]) 
    
    return result
        
if p == 0:
    odd = 0
    for i in range(a_odd//2 + 1):
        odd += cmb(a_odd, 2 * i)
    print((2 ** (a_even)) * odd)
else:
    odd = 0
    if a_odd % 2 == 0:
        for i in range(a_odd//2):
            odd += cmb(a_odd, 2 * i + 1)
    else:
        for i in range(a_odd//2 + 1):
            odd += cmb(a_odd, 2 * i + 1)
    print((2 ** (a_even)) * odd)

Solution (Python):
N = 52  
fact = [1, 1]  

for i in range(2, N + 1):
    fact.append(fact[-1] * i)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return (fact[n] // fact[r]) // fact[n-r] 

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

cnt = [0,0]
for i in range(N):
    cnt[A[i]%2] += 1

ans = 2**(cnt[0])
mm = 0
if P==0:
    for i in range(0,cnt[1]+1,2):
        mm += cmb(cnt[1],i)
else:
    for i in range(1,cnt[1]+1,2):
        mm += cmb(cnt[1],i)

print(ans*mm)

Solution (Python):
import math
N,P=map(int,input().split())
A=list(map(int,input().split()))
l=[]
c=0
cnt=0
even=0
odd=0
for i in range(0,N):
    if A[i]%2==0:
        even=even+1
    else:
        odd=odd+1
if P==0:
    print(pow(2,even)*max(pow(2,odd-1),1))
else:
    print(pow(2,even)*math.floor(pow(2,odd-1)))

Solution (Python):
import math
n, p = map(int, input().split())
a = list(map(int, input().split()))
def combi(x, y):
    if y == 0:
        return 1
    if x == 0:
        return 0
    return math.factorial(x) / (math.factorial(x - y) * math.factorial(y))
odd_count = 0
even_count = 0
for i in range(n):
    if a[i] % 2 == 0:
        even_count += 1
    else:
        odd_count += 1
ans = 0
if p % 2 == 0:
    ans += pow(2,even_count)
    tmp = 0
    for i in range(0,odd_count+1,2):
        tmp += combi(odd_count,i)
    ans *= tmp
else:
    ans += pow(2,even_count)
    tmp = 0
    for i in range(1,odd_count+1,2):
        tmp += combi(odd_count,i)
    ans *= tmp
print(int(ans))

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


def print_matrix(mat):
    for i in range(len(mat)):
        print(*mat[i])


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()

nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']



show_flg = False


def main():
    N, P = MI()
    A = LI()
    total = sum(A)
    dp = [0] * (total+1)
    dp[0] = 1

    
    
    
    
    
    
    

    

    for i in range(N):
        dp_next = [0] * (total+1)
        for j in range(total+1):
            if dp[j] >= 1:
                dp_next[j] = max(dp[j], dp_next[j])
                if j + A[i] <= total:
                    dp_next[j+A[i]] = dp[j+A[i]]
                    dp_next[j+A[i]] += dp[j]
                
        
        dp = dp_next

    ans = 0
    for i in range(total+1):
        if i % 2 == P:
            ans += dp[i]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from math import factorial
def c(n,k):
  return factorial(n)//factorial(k)//factorial(n-k)
n,p=map(int,input().split())
a=list(map(int,input().split()))
odd=0
for i in a:
  if i%2==1:
    odd+=1
even = n-odd
m = (odd // 2) + 1
even_ = pow(2,even)
odd_ = 0
for i in range(m):
  odd_ += c(odd,i*2)
if p==0:
  print(even_ * odd_)
else:
  print(pow(2,n)-even_ * odd_)

Solution (Python):
from operator import mul
from functools import reduce
def sml_cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    n, p = map(int, input().split())
    a = list(map(int, input().split()))
    cnt_ev = 0
    cnt_od = 0
    for v in a:
        if v % 2 == 0:
            cnt_ev += 1
        else:
            cnt_od += 1
    if p == 0:
        x, y = 0, 0
        for i in range(cnt_ev+1):
            x += sml_cmb(cnt_ev, i)
        for i in range(0, cnt_od+1, 2):
            y += sml_cmb(cnt_od, i)
        print(x*y)
    else:
        x, y = 0, 0
        for i in range(cnt_ev+1):
            x += sml_cmb(cnt_ev, i)
        for i in range(1, cnt_od+1, 2):
            y += sml_cmb(cnt_od, i)
        print(x*y)

if __name__ == "__main__":
    main()

Solution (Python):
n,p = map(int,input().split())
a = list(map(int,input().split()))
odd = [i for i in a if i%2==1]
eve = [i for i in a if i%2==0]
odd_len = len(odd)
eve_len = len(eve)
if p==0:
    ans = 2**eve_len
else:
    ans = 0
count = 0
if p==0:
    if odd_len!=0:
        ans *= 2**odd_len//2
else:
    ans +=   (2**eve_len)*(2**odd_len//2)
print(ans)

Solution (Python):
N,P=map(int,input().split())
A=list(map(int,input().split()))
a=0
for i in A:
  if i%2==0:
    a+=1
b=N-a
c=0
import math
def comb(n,r):
  return math.factorial(n) // (math.factorial(n-r)*math.factorial(r))  
for i in range(b//2+1):
  c+=comb(b,2*i)
if P==0:
  print((2**a)*c)
else:
  print(2**N-(2**a)*c)

Solution (Python):
def main():
  n, p = input_list()
  a = list(input_list())
  
  is_even = True
  for v in a:
    if v % 2 != 0:
      is_even = False
      break
  if is_even:
    if p == 0:
      print(2**n)
      exit()
    else:
      print(0)
      exit()
  else:
    print(2**(n-1))
  
  exit()
  if p == 0:
    
    for i in range(n):
      if i % 2 == 0:
        r += combinations_count(n, i)
    if r % 2 != 0:
      r += 1
  else:
    
    for i in range(n):
      if i % 2 != 0:
        r += combinations_count(n, i)
    if r > 0:
      r += 1
  print(r)  
  exit()
  for i in range(bi+1):
    fi = format(i, '0'+str(n)+'b')
    ans = 0
    for index, v in enumerate(fi):
      if v == '1':
        ans += a[index]
    if ans % 2 == p:
      r += 1
  print(r)
  
def input_list():
  return map(int, input().split())

def input_list():
  return map(int, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

import math
import fractions

from functools import reduce
main()

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

odd = 0
even = 0

for ai in A:
    if ai % 2 == 0:
        even += 1
    else:
        odd += 1

if odd == 0:
    if P == 1:
        ans = 0
    else:
        ans = (2 ** even) 
else:
    ans = (2 ** even) * ((2 ** odd) // 2)

print(ans)

Solution (Python):
n, p = map(int, input().split())
a = list(map(int, input().split()))
flag = True
for i in a:
    if i % 2 == 0:
        continue
    else:
        flag = False
        break

if n == 1 and a[0] % 2 == 0:
    if p == 0:
        print(2)
    else:
        print(0)
elif n == 1 and a[0] % 2 == 1:
    print(1)

else:
    if flag:
        if p == 0:
            print(2 ** n)
        else:
            print(0)
    else:
        print(2 ** n // 2)

Solution (Python):
n,k = map(int,input().split())
lst = list(map(int,input().split()))
e,o = 0,0
for i in range(n):
    if lst[i]%2==0:
        e += 1
    else:
        o += 1

if o==0:
    if k==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))