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
input = sys.stdin.readline

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

    pre = [1, 0]

    for i, a in enumerate(A):
        if a&1:
            tmp = [sum(pre), sum(pre)]
        else:
            tmp = [pre[0] * 2, pre[1] * 2]
        pre = tmp
    
    print(pre[P])

if __name__ == "__main__":
    main()

Solution (Python):
from math import factorial
def f(a, b):
    if a == 0 or b == 0:
        return 1
    else:
        return factorial(a) // (factorial(a - b) * factorial(b))
n, p = map(int, input().split())
a = [int(x) % 2 for x in input().split()]
e, o = a.count(0), a.count(1)
if p == 0:
    print((2**e)*sum([f(o, i) for i in range(0, o+1, 2)]))
else:
    print((2**e)*sum([f(o, i) for i in range(1, o+1, 2)]))

Solution (Python):
n,p = map(int, input().split())
a = list(map(int, input().split( )))
a = [a[i]%2 for i in range(n)]
dp0 = 1
dp1 = 0

for i in range(n):
    if a[i]%2:
        dp_0 = dp1 + dp0
        dp_1 = dp1 + dp0
    
        dp0,dp1 = dp_0,dp_1
    else:
        dp0*=2
        dp1*=2

if p:
    print(dp1)
else:
    print(dp0)

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

if sum(A) == 0:
    if P == 0:
        print(pow(2, N))
    else:
        print(0)
else:
    print(pow(2, N-1))

Solution (Python):
n, p = map(int, input().split())
A = list(map(int, input().split()))
A = [a%2 for a in A]
if sum(A) == 0:
    print(pow(2, n) if p==0 else 0)
elif n>=2:
    print(pow(2, n)//2)
else:
    print(1 if A[0]==p else 0)

Solution (Python):
def cmb(n,r):
    if n==0 or r==0:
        return 1
    else:
        ans=1
        for i in range(1,min(r,n-r)+1):
            ans=ans*(n-i+1)//i
        return ans

n,p=map(int,input().split())
a=list(map(int,input().split()))
buf=0
for i in range(n):
    if a[i]%2==1:
        buf+=1
ans=0
if p==0:
    for i in range(buf//2+1):
        ans+=cmb(buf,2*i)
    ans*=2**(n-buf)
    print(ans)
else:
    for i in range((buf+1)//2):
        ans+=cmb(buf,2*i+1)
    ans*=2**(n-buf)
    print(ans)

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

num_odd = 0
num_even = 0
for a in A:
    if a % 2 == 0:
        num_even += 1
    else:
        num_odd += 1


def cmb(n, r):
    ans = 1
    for i in range(r):
        ans *= n
        n -= 1
    ans1 = 1
    for i in range(1, r + 1):
        ans1 *= i
    return ans // ans1

ans = 0

if P == 0:
    select_odd = 0
    for i in range(0, num_odd + 1, 2):
        select_odd += cmb(num_odd, i)
    for i in range(0, num_even + 1):
        ans += cmb(num_even, i) * select_odd
else:
    select_odd = 0
    for i in range(1, num_odd + 1, 2):
        select_odd += cmb(num_odd, i)
    for i in range(0, num_even + 1):
        ans += cmb(num_even, i) * select_odd
print(ans)

Solution (Python):
N,P,*A=map(int, open(0).read().split())
o=sum(a&1 for a in A)
e=N-o

ans = 0
for i in range(1,o+1,2):
    res = 1
    for r in range(i):
        res *= o-r
        res //=r+1
    ans += res
ans*=2**e
if not P:
    ans=2**N-ans
print(ans)

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

odd = []
even = []
ans = 0
for i in A:
  if (i % 2 == 1):
    odd.append(i)
  else:
    even.append(i)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
  
if (P == 0):
  l_odd = len(odd)
  num = 0
  while l_odd >= num:
    ans += combinations_count(l_odd, num)
    num += 2
  if (len(even)!=0):
    ans *= 2**len(even)
else:
  l_odd = len(odd)
  num = 1
  while l_odd >= num:
    ans += combinations_count(l_odd, num)
    num += 2
  if (len(odd)!=0):
    ans *= 2**len(even)
print(ans)

Solution (Python):
import math,itertools

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

def main():
    N,P = map(int,input().split())
    A = list(map(int,input().split()))
    odd_A = [A[i] for i in range(N) if A[i]%2 != 0]
    even_A = [A[i] for i in range(N) if A[i]%2 == 0]
    allpat = 2**N
    comb = 0
    for i in range(0,len(odd_A)+1,2):
        comb += combinations_count(len(odd_A),i)
    evenpat = (2**len(even_A))*comb
    oddpat = allpat - evenpat
    ans = oddpat if P == 1 else evenpat
    print(ans)


if __name__ == '__main__':
    main()

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

if p==0:
    ans=2**n
else:ans=0
    
for i in range(n):
    if a[i]%2!=0:
        ans=2**(n-1)
        break
print(ans)

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

odd = sum([item % 2 for item in a])
even = n - odd

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

Solution (Python):
n, p = map(int, input().split())
a = [_ % 2 for _ in [int(_) for _ in input().split()]]
num_zero = 0
num_one = 0
for _ in a:
    if _ == 0:
        num_zero += 1
    else:
        num_one += 1


ans = 0
if p == 0:
    if num_one == 0:
        ans = 2 ** n
    else:
        ans = 2 ** (n - 1)
else:
    if num_one == 0:
        ans = 0
    else:
        ans = 2 ** (n - 1)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
INF = 1<<32

MOD = 2  

def solve(N: int, P: int, A: "List[int]"):

    if all([i%2 == 0 for i in A]):
        if P == 0:
            print(2**N)
        else:
            print(0)

    else:
        od = len([i%2 == 1 for i in A])
        print(2**(N-1))

    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):
from operator import mul
from functools import reduce


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

LLeven = map(lambda x: x % 2, L)
LLodd = map(lambda x: x % 2, L)

even = list(LLeven).count(0)
odd = list(LLodd).count(1)

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


def pattern(x):
    (choose_even,choose_odd) = (0,0)
    for i in range(x+1):
        if i%2 == 0:
            choose_even += cmb(x,i)
        else:
            choose_odd += cmb(x,i)
    return(choose_even,choose_odd)

if p == 0:
    print(2**even * pattern(odd)[0])
else:
    print(2**even * pattern(odd)[1])

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

if all(a%2==0 for a in A):
  if P==0:
    print 2**N
  else:
    print 0
else:
  print 2**N/2

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

odd = [a%2 for a in A].count(1)
even = N-odd

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

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

odd = [a%2 for a in A].count(1)
even = N - odd
if odd == 0:
    print(0 if P else 2**N)
else:
    print(2**(N-1))

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

odd = [a % 2 == 1 for a in A].count(True)
even = N - odd

C = [[0] * 51 for i in range(51)]
C[0][0] = 1
for i in range(1, 51):
    C[i][0] = 1
    for j in range(1, i + 1):
        C[i][j] = C[i - 1][j - 1] + C[i - 1][j]

if P == 1 and odd == 0:
    print(0)
else:
    x = 2 ** even
    y = 0
    i = P
    while i <= odd:
        y += C[odd][i]
        i += 2
    print(x * y)

Solution (Python):
n, p, *a = map(int, open(0).read().split())
even = odd = 0
for i in a:
    if i%2: odd += 1
    else: even += 1
ecr = [1] * (even+1)
for i in range(1, even): ecr[i] = ecr[i-1]*(even-i+1)//i
ocr = [1] * (odd+1)
for i in range(1, odd): ocr[i] = ocr[i-1]*(odd-i+1)//i
print(sum(ecr) * sum(ocr[p::2]))

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

odd=0
even=0
for i in range(0,N):
    if A[i]%2==1:
        odd=odd+1
    else:
        even=even+1
if odd==0:
    if P==0:
        print(2**(even))
    else:
        print(0)
else:
    print((2**(odd-1))*(2**(even)))

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

dp = [[None for remainder in range(2)] for i in range(N + 1)]
dp[0][0] = 1
dp[0][1] = 0

for i in range(N):
    for r in range(2):
        dp[i + 1][r] = dp[i][r] + dp[i][(r + A[i]) % 2]

print(dp[N][P])

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

flag = True
for a in A:
    if a % 2 != 0:
        flag = False

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

print(ans)

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

for a in al:
    if a % 2 == 1:
        print(2**(n-1))
        exit()

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

Solution (Python):
from sys import stdin

n,p = [int(x) for x in stdin.readline().rstrip().split()]
li = list(map(int,stdin.readline().rstrip().split()))

if all(i%2 == 0 for i in li):
    if p == 0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

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

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

even_num=0
odd_num=0

for a in A:
    if a%2==0:
        even_num+=1
    else:
        odd_num+=1

ev_case = 2**even_num


from math import factorial

res=0
for i in range(P,odd_num+1,2):                                                                   res += factorial(odd_num) / factorial(i) / factorial(odd_num - i)

print(int(ev_case*res))

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

flg = True
for a in alist:
    if a % 2 != 0:
        flg = False
        break
if flg:
    if P == 0:
        print(2**N)
    else:
        print(0)
else:
    print(2**(N - 1))

Solution (Python):
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial, ceil, floor
from collections import defaultdict
import itertools
sys.setrecursionlimit(200000)
input = sys.stdin.readline









N, M, = map(int, input().split())
L = [int(v) % 2 for v in input().split()]
L.sort()

zc = len([v for v in L if v == 0])
oc = len([v for v in L if v == 1])

if oc == 0:
    if M == 0:
        print(2 ** N)
    else:
        print(0)
else:
    print(2 **  (N - 1))

Solution (Python):
N, P = map(int, input().split())
A = list(map(int, input().split()))
a = [i%2 for i in A]
zero = a.count(0)
one = a.count(1)

if one == 0 and P == 1:
    print(0)
else:
    print( (2**zero) * (2**(max(0, one-1))) )

Solution (Python):
DP = [[0 for _ in range(2)] for _ in range(55)]
DP[0][0] = 1
N, P, *A = map(int, open(0).read().split())
for i in range(N):
  DP[i+1][0] += DP[i][0]
  DP[i+1][0] += DP[i][A[i]%2]
  DP[i+1][1] += DP[i][1]
  DP[i+1][1] += DP[i][(A[i]%2)^1]
print(DP[N][P])

Solution (Python):
import math


def combinations_count(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()))
odd_num = 0
even_num = 0
for a in A:
    if a % 2 == 1:
        odd_num += 1
    else:
        even_num += 1
ans = 0

if P == 1:
    if odd_num == 0:
        ans = 0
    else:
        for i in range(1, N + 1, 2):
            ans += combinations_count(N, i)
else:
    if odd_num == 0:
        ans = 2 ** even_num
    else:
        for i in range(0, N + 1, 2):
            ans += combinations_count(N, i)
print(ans)

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

jug = True
for i in range(n):
    if a[i] % 2 == 1:
        jug = False
        break

if jug:
    if p == 0:
        print(2 ** n)
    else:
        print(0)
else:
    print(2 ** (n - 1))

Solution (Python):




n, p = map(int, input().split())
odds = n - len(list(filter(lambda x: int(x) % 2 == 0, input().split())))
evens = n - odds


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


ans = 0
if p == 0:
    for i in range(0, odds + 1, 2):
        ans += ncr(odds, i)
    if evens > 0:
        ans *= max(1, 2 ** evens)
else:
    if odds > 0:
        for i in range(1, odds + 1, 2):
            ans += ncr(odds, i)
        ans *= max(1, 2 ** evens)
print(ans)

Solution (Python):
n,p=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
f=0
for i in a:
    if i%2!=0:
        f=1
if f==0:
    if p==0:
        print(2**n)
    else:
        print(0)
else:
    print(2**(n-1))

Solution (Python):
import sys
input = sys.stdin.readline



mod = 10**9+7 
N = 2*10**5 + 1

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 



def main():
    
    N,P = map(int, input().split())
    
    vA = list(map(int, input().split()))
    
    
    dp = [1, 0]
    print(dp, file=sys.stderr)
    for i,c in enumerate(vA,1):
        a = c%2
        p0, p1 = dp[a], dp[1^a]
        dp[0] += p0
        dp[1] += p1
    print(dp, file=sys.stderr)
    print(dp[P])
    
    
    
    
    
    


if __name__ == "__main__":
    main()

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

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

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

print(dp[N][P])

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

odd = 0
even = 0

for i in range(n):
    if ls[i] % 2 == 0:
        even += 1
    elif ls[i] % 2 == 1:
        odd += 1

if p == 0:
    print((2 ** even) * max(2 ** (odd - 1), 1))
elif p == 1:
    if odd == 0:
        print(0)
    else:
        print((2 ** even) * max((2 ** (odd - 1), 1)))

Solution (Python):

"""
- Aは奇数か偶数かだけ分かれば良い
- Pが0でも1でも計算内容はそんなに変わらない
奇数がk個のとき、P=1の解はどうなるか
1 1C1
2 2C1
3 3C1+3C3
4 4C1+4C3
5 5C1+5C3+5C5
にそれぞれ2^(偶数の数)
"""
from math import factorial
def comb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)
n, p = map(int, input().split())
A = list(map(int, input().split()))
even = 0
odd = 0
for a in A:
    if a%2==0:
        even+=1
    else:
        odd+=1
ans = 0
for k in range(1,odd+1,2):
    ans += comb(odd,k)
ans *= 2**even
if p==0:
    print (2**n-ans)
else:
    print (ans)

Solution (Python):
N, P = map(int, input().split())
O = sum([int(a) % 2 for a in input().split()])
E = N - O
fa = [1]
for i in range(1, 51):
    fa.append(fa[-1] * i)
ans = 0
for i in range(P, O+1, 2):
    ans += fa[O] // (fa[i] * fa[O-i])

print(ans * 2**E)

Solution (Python):
def fact(x):
    if x == 0 or x == 1:
        return 1

    ans = 1
    for i in range(1,x+1):
        ans *= i
    return ans
def combi(n,r):
    return fact(n)//((fact(r))*(fact(n-r)))

N, P = map(int,input().split())
A = list(map(lambda x: int(x)%2,input().split()))
cnt1 = A.count(1)
t = P
sumC = 0
while  t <= cnt1:
    sumC += combi(cnt1,t)
    t += 2
print(sumC*(2**(N-cnt1)))

Solution (Python):
N,P=map(int,input().split())
A = list(map(int,input().split()))
x = sum([1 for i in A if i%2==0])
y = N - x

ans = (2**x) * (2**max(0,y-1))

if P == 1:
  ans = (2**x)*(2**y)-ans
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools
from math import factorial
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10


def solve():
    n, p = LI()
    a = LI()
    odd = sum(map(lambda x: x & 1, a))
    even = sum(map(lambda x: (x ^ 1) & 1, a))
    t0 = 0
    t1 = 0
    for i in range(0, odd + 1, 2):
        a = factorial(odd)
        b = factorial(i)
        c = factorial(odd - i)
        t0 += a // b // c
    for i in range(1, odd + 1, 2):
        a = factorial(odd)
        b = factorial(i)
        c = factorial(odd - i)
        t1 += a // b // c
    print(2 ** even * t1 if p else 2 ** even * t0)
    return



if __name__ == '__main__':
    solve()

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

Solution (Python):
n,p=map(int,input().split())
a=list(map(int,input().split()))
even=len([a[i] for i in range(len(a)) if a[i]%2==0])
odd=len([a[i] for i in range(len(a)) if a[i]%2!=0])

def make_c(n):
	nck=[1]
	child=n
	mother=1
	for i in range(1,n+1):
		nck.append(nck[i-1]*child//mother)
		child-=1
		mother+=1
	return nck
	


if(p==0):
	comb=make_c(odd)
	comb=comb[0::2]
	odd_comb=sum(comb)	
	ans=(2**even)*odd_comb
else:
	comb=make_c(odd)
	comb=comb[1::2]
	odd_comb=sum(comb)
	ans=(2**even)*odd_comb	
print(ans)

Solution (Python):
class combination():
    
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def examA():
    N, P = LI()
    A = LI()
    odd = 0; even = 0
    for a in A:
        if a%2==1:
            odd +=1
        else:
            even +=1
    C = combination(N,mod)
    ans = 0
    if P==1:
        for i in range((odd+1)//2):
            ans += 2**even * C.comb(odd,i*2+1,mod)
    else:
        for i in range(odd//2+1):
            ans += 2**even * C.comb(odd,i*2,mod)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examA()

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

odd = False
for a in A:
    if a % 2 == 1:
        odd = True
        break

if odd:
    print(2**(n-1))
elif p == 0:
    print(2**n)
else:
    print(0)

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

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

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


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


ans = 2**even
cnt = 0
if p == 0:
    for i in range(0, odd+1, 2):
        cnt += cmb(odd, i)
else:
    for i in range(1, odd+1, 2):
        cnt += cmb(odd, i)

print(ans*cnt)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,P,*A = map(int,read().split())

od,ev = 0,1
for x in A:
    if x & 1:
        od,ev = od+ev,od+ev
    else:
        od,ev = od+od,ev+ev

answer = od if P else ev
print(answer)

Solution (Python):
import math
N,P = map(int,input().split())
A = [i%2 for i in list(map(int,input().split()))]
odd,even = A.count(1),A.count(0)
sumo = 0
for i in range(P,odd+1,2):
    sumo += int(math.factorial(odd)//(math.factorial(odd-i)*math.factorial(i)))
print(sumo*(2**even))

Solution (Python):
import math
N,P = map(int,input().split())
A = list(map(int,input().split()))
A = [i%2 for i in A]
odd = A.count(1)
even = A.count(0)
sumo = 0
for i in range(odd+1):
    if i%2 == P:
        sumo += int(math.factorial(odd)//(math.factorial(odd-i)*math.factorial(i)))
print(sumo*(2**even))

Solution (Python):
import math
N,P = map(int,input().split())
A = list(map(int,input().split()))
A = [i%2 for i in A]
odd = A.count(1)
even = A.count(0)
sumo = 0
for i in range(odd+1):
    if i%2 == P:
        sumo += int(math.factorial(odd)//(math.factorial(odd-i)*math.factorial(i)))
ans = sumo*(2**even)
print(ans)

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

Solution (Python):
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
n,p=map(int,input().split())
a=list(map(int,input().split()))
cnt=0
odd=0
even=0
ans=0
for i in range(n):
    if a[i]%2==0:
        even+=1
    else:
        odd+=1
if p==0:
    cnt=odd
    if cnt%2!=0:
        cnt-=1
    while cnt>=0:
        ans+=combinations_count(odd, cnt)
        cnt-=2
    ans*=2**even
else:
    cnt=odd
    if cnt%2==0:
        cnt-=1
    while cnt>=0:
        ans+=combinations_count(odd, cnt)
        cnt-=2
    ans*=2**even
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()))
o=0
e=0
for i in a:
    if i%2==0:
        e+=1
    else:
        o+=1
ans=2**e
cnt=0
if p==0:
    for i in range(0,o+1,2):
        cnt+=comb(o,i)
    print(ans*cnt)
else:
    for i in range(1,o+1,2):
        cnt+=comb(o,i)
    print(ans*cnt)

Solution (Python):

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

f0, f1 = 0, 0
for a in A:
    if a % 2 == 0:
        f0 += 1
    else:
        f1 += 1

ans = 0
n = 2 ** f0
for i in range(P, f1+1, 2):
    m = 1
    for j in range(i):
        m *= f1 - j
    for i in range(i):
        m /= i + 1

    ans += m * n

print(int(ans))

Solution (Python):
n,p=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(n+1)
if a[0]%2==1:
  dp[1]=1
elif a[0]%2==0 and p==1:
  dp[1]=0
else:
  dp[1]=2
for i in range(1,n):
  if a[i]%2==1:
    dp[i+1]=2**(i)
  else:
    dp[i+1]=2*dp[i]
print(dp[n])

Solution (Python):
import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	
	sys.stdin = open(name)

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



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



if ki==0:
	if p==1:
		print(0)
		exit()
	elif p==0:
		print(int(2**n))
		exit()

ans = 2**gu * (2**ki)/2
print(int(ans))

Solution (Python):
N, P = map(int,input().split())
A = list(map(int,input().split()))
odd = len(list(filter(lambda x:x%2==1 ,A)))
even = N-odd
if odd == 0:
    if P == 0:print(2**(N))
    else:print(0)
else:
    print(2**(N-1))

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

o, e = 0, 0
for i in range(N) :
  if A[i] % 2 == 0 :
    e += 1
  else :
    o += 1

ret = pow(2, e) * max(1, pow(2, o - 1))

if P == 0 :
  print(ret)
else :
  print(pow(2, N) - ret)

Solution (Python):
n,p = map(int,input().split())
L = list(map(int,input().split()))
Le = [x for x in L if x%2 == 0]
Lo = [x for x in L if x%2 == 1]

if p == 0:
    if len(Lo) == 0:
        print(2**n)
    else:
        print(2**(n-1))
if p == 1:
    if len(Lo) == 0:
        print(0)
    else:
        print(2**(n-1))

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

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

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

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


ki=0

for i in a:
    if i%2 != 0:
        ki=1
        break

if ki==0:
    if p==0:
        ans=2**n
    else:
        ans=0
else:
    ans=2**(n-1)
print(ans)

Solution (Python):
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, p = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    ls = [0] * 5001
    ls[0] += 1
    for v in a:
        for i in range(5000 - v, -1, -1):
            ls[i+v] += ls[i]
    t = 0
    for i in range(p, 5001, 2):
        t += ls[i]
    print(t)


if __name__ == '__main__':
    solve()

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

print(int(ans))

Solution (Python):
from math import factorial

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

ans = 0
for i in range(odd+1):
    if i%2 == P:
        ans += factorial(odd) / factorial(i) / factorial(odd-i)
ans *= 2**even

print(int(ans))

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

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

odd = []
even = []
for i in a:
    if i % 2 != 0:
        odd.append(i)
    else:
        even.append(i)
if len(odd) == 0:
    if p == 1:
        ans = 0
    else:
        ans = 2 ** len(even)
else:
    ans = 2 ** len(even) * 2 ** (len(odd) - 1)
print(ans)

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

for i in a:
    if i & 1:
        odd.append(i)
    else:
        even.append(i)
n_odd = len(odd)
n_even = len(even)


def nCr(n, r):
    r = min(r, n - r)
    ans = 1
    denom = 1
    for i in range(1, r + 1):
        ans *= n-(i-1)
        denom *= i
    return ans//denom



if p == 0:
    ans = 2 ** n_even
    tmp = 0
    for i in range(0, n_odd + 1, 2):
        tmp += nCr(n_odd, i)
    ans *= tmp
else:  
    ans = 2 ** n_even
    tmp = 0
    for i in range(1, n_odd + 1, 2):
        tmp += nCr(n_odd, i)
    ans *= tmp

print(ans)

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

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

g=k=0
for i in a:
    if i % 2 == 0 : g+=1
    elif i % 2 == 1 : k+=1

all_g = all_k =0
for i in range(g+1):
    all_g += cmb(g,i)
        
if p == 0:
    for i in range(0,k+1,2):
        all_k += cmb(k,i)
elif p == 1:
    for i in range(1,k+1,2):
        all_k += cmb(k,i)
print(all_g * all_k)

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

x = 0
y = 0

for c in a:
    if c % 2 == 1:
        x += 1
    else:
        y += 1

if x == 0 and p == 1:
    print(0)
    exit()
elif x == 0:
    print(2 ** y)
    exit()
else:
    print(2 ** y * (2 ** (x-1)))

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

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


def use(i, j):
    if i >= n:
        return 1 if j == p else 0
    if dp[i][j] != -1:
        return dp[i][j]
    dp[i][j] = use(i+1, j)+use(i+1, (j+a[i]) % 2)
    return dp[i][j]


print(use(0, 0))

Solution (Python):
from math import factorial

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

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

o = 0
e = 0

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

a = []
b = []
ans = 0

if P == 0:
    for i in range(e+1):
        a.append(c(e,i))
    for i in range(on+1):
        b.append(c(o,i*2))        
    for i in a:
        for j in b:
            ans += i * j
else:
    for i in range(e+1):
        a.append(c(e,i))
    for i in range(1,o+1)[::2]:
        b.append(c(o,i))        
    for i in a:
        for j in b:
            ans += i * j

ans = int(ans)
print(ans)