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):
N, P = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0,0] for k in range(N+1)]
dp[0][0] = 1
for k in range(N):
    if A[k]%2 == 0:
        dp[k+1][0] = dp[k][0]*2
        dp[k+1][1] = dp[k][1]*2
    else:
        dp[k+1][0] = dp[k][0] + dp[k][1]
        dp[k+1][1] = dp[k][1] + dp[k][0]

print(dp[N][P])

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

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

Solution (Python):
def solve():
  N, P = map(int, input().split())
  A = list(map(int, input().split()))
  zero,one = 0,0
  for i in range(N):
    if A[i]%2==0:
      zero += 1
    else:
      one += 1
  ans = pow(2,N-1)
  if P==1 and one == 0:
    return 0
  if P==0 and one == 0:
    return pow(2,N)
  return ans
print(solve())

Solution (Python):
import math

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

remainders = [a%2 for a in A]

odd = remainders.count(1)
even = remainders.count(0)

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

ans = 0
for n in range(N+1):
  for p in range(P,n+1,2):
    if odd >= p and even >= n-p:
      ans += combinations_count(odd,p) * combinations_count(even,n-p)

print(ans)

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

n0 = sum(1 for a in la if a % 2 == 0)
n1 = sum(1 for a in la if a % 2 == 1)


def combi(n, k):
    c = 1
    for i in range(1, n + 1):
        c *= i
    for i in range(1, k + 1):
        c //= i
    for i in range(1, n - k + 1):
        c //= i
    return c


def answer():
    if p == 0:
        c0 = 2 ** n0
        c1 = 0
        for i in range(0, n1 + 1, 2):
            c1 += combi(n1, i)
        return c0 * c1
    else:
        c0 = 2 ** n0
        c1 = 0
        for i in range(1, n1 + 1, 2):
            c1 += combi(n1, i)
        return c0 * c1

print(answer())

Solution (Python):
from math import factorial as fa
def comb(n, r):
    return fa(n)//(fa(n-r)*fa(r))
n, p = map(int, input().split())
A = list(map(lambda x:int(x)%2, input().split()))
even = A.count(0)
odd = A.count(1)
ans = 0
for i in range(p,odd+1,2):
    ans += comb(odd, i)
print(ans*pow(2,even))

Solution (Python):
from collections import Counter

MOD = 10**9+7
MAX_N = 50
inv = [0] * (MAX_N+1)
finv = [0] * (MAX_N+1)
fac = [0] * (MAX_N+1)
inv[1] = 1
finv[0] = 1; finv[1] = 1
fac[0] = 1; fac[1] = 1

def COM_init():
    for i in range(2, MAX_N+1):
        inv[i] = -(MOD//i)*inv[MOD%i]%MOD
        finv[i] = finv[i-1]*inv[i]%MOD
        fac[i] = fac[i-1]*i%MOD

def COM(a, b):
    if a < 0 or b < 0:return 0
    if a < b:return 0
    
    return fac[a]*finv[a-b]*finv[b]%MOD

def main():
    N, P = map(int, input().split())
    A = list(map(int, input().split()))
    B = [a%2 for a in A]
    c = Counter(B)
    
    n0 = c[0]
    n1 = c[1]
    ans = 0
    COM_init()
    for i in range(P, n1+1, 2):
        ans += pow(2, n0) * COM(n1, i)

    print(ans) 
         

if __name__ == "__main__":
    main()

Solution (Python):

n, p, *a = map(int, open(0).read().split())
dp = [0] * (n + 1)
dp[0] = 1 if p == 0 else 0
for i in range(1, n + 1):
    if a[i - 1] % 2:
        dp[i] = 2**(i - 1)
    else:
        dp[i] = 2 * dp[i - 1]
print(dp[n])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, P = getNM()
A = getList()
for i in range(N):
    if A[i] % 2 == 0:
        A[i] = 0
    else:
        A[i] = 1

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

for i in range(1, N):
    if A[i] == 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 - 1][P])

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

def f(s):
    n = int(s)%2
    return n

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

c0 = A.count(0)
c1 = A.count(1)
fact = [1]* (c1+1)
for i in range(1,c1+1):
    fact[i]= fact[i-1]*i

cnt = 0
for i in range(P,c1+1,2):
    cnt += fact[c1]//fact[i]//fact[c1-i]

print(cnt*pow(2,c0))

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


def read():
    N, P = map(int, input().strip().split())
    A = list(map(int, input().strip().split()))
    return N, P, A


def binom_64bit(n):
    c = [1 for i in range(n+1)]
    for k in range(1, n):
        c[k] = c[k-1] * (n-k+1) // k
    return c


def solve(N, P, A):
    B = Counter([a % 2 for a in A])
    C0 = binom_64bit(B[0])
    C1 = binom_64bit(B[1])
    ans = 0
    if P == 1:
        for i in range(0, B[0]+1):
            for j in range(1, B[1]+1, 2):
                ans += C0[i] * C1[j]
    else:
        for i in range(0, B[0]+1):
            for j in range(0, B[1]+1, 2):
                ans += C0[i] * C1[j]
    return ans


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from math import comb

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

    zero = 0
    one = 0

    for x in a:
        if x % 2 == 0:
            zero += 1
        else:
            one += 1

    ans = 0
    q = 2 ** zero

    if p == 0:
        for x in range(0, one + 1, 2):
            ans += q * comb(one, x)
    else:
        for x in range(1, one + 1, 2):
            ans += q * comb(one, x)

    print(ans)


if __name__ == '__main__':
    main()

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

for a in A:
  if a % 2 != 0:
    break 
else:
  if p == 1: 
    print(0)
    exit()
  if p == 0: 
    print(2**n)
    exit()
  
ans = 2**(n-1)
print(ans)

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

for a in A:
  if a % 2 != 0:
    break 
else:
  if p == 1: 
    print(0)
    exit()
  if p == 0: 
    print(2**n)
    exit()
  
ans = 2**(n-1)
print(ans)

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

def comb(n, r):
    ans = 1
    if n < 2*r:
        r = n - r
    for i in range(r):
        ans *= (n - i)
        ans //= (i + 1)
    return ans

ev, od = 0, 0
for i in a:
    if i%2 == 0:
        ev += 1
    else:
        od += 1
ans = 0
if p == 0:
    for i in range(0, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j)
else:
    for i in range(1, od+1, 2):
        for j in range(ev+1):
            ans += comb(od, i)*comb(ev, j) 
print(ans)

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


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


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

Solution (Python):
import math
n,p=map(int,input().split())
c=0
for m in map(int,input().split()):
  if m%2==0:c+=1
d=2**(c)

e=0
for i in range(p,n-c+1,2):
  
  k=math.factorial(n-c) // (math.factorial(n-c - i) * math.factorial(i))
  k=max(k,1)
  e+=k

print(d*e)

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

ans = 0
mlt = 2 ** (N-div)
if P == 0:
  for i in range(0, div+1, 2):
    cmb = math.factorial(div) // (math.factorial(div-i) * math.factorial(i))
    ans += cmb * mlt
else:
  for i in range(1, div+1, 2):
    cmb = math.factorial(div) // (math.factorial(div-i) * math.factorial(i))
    ans += cmb * mlt
    
print(ans)

Solution (Python):
N, P = map(int, input().split())
As = list(map(int, input().split()))
dic = {0:0, 1:0}
for a in As:
  if a % 2 == 0:
    dic[0] += 1
  else:
    dic[1] += 1

if P == 1 and dic[1] == 0:
  print(0)
  exit()
  
rlt = 2**dic[0]
tmp = 0
for i in range(dic[1]+1):
  if i == 0:
    t = 1
  else:
    t = t*(dic[1]+1-i)//i
  if (P == 0 and i%2==0) or (P == 1 and i%2==1):
    tmp += t
      
rlt *= tmp

print(rlt)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

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

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

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd





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


t = 1

for case in range(1,t+1):
    ans = solve()


"""

"""

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

dp = [0] * 5005
dp[0] = 1

for a in A:
    for i in range(5000, 0, -1):
        if i - a >= 0:
            dp[i] += dp[i - a]

print(sum(dp[i] for i in range(len(dp)) if i % 2 == P))

Solution (Python):
N, P = map(int, input().split())
a_li = list(map(int, input().split()))
ans = 0
o = 0
for a in a_li:
    if a % 2 != 0:
        o += 1
if o == 0:
    if P == 1:
        ans = 0
    else:
        ans = 2 ** N
else:
    ans = 2 ** (N - 1)
print(ans)

Solution (Python):
def resolve():
    '''
    code here
    '''
    N, P = [int(item) for item in input().split()]
    As = [int(item)%2 for item in input().split()]

    is_all_even = True
    for item in As:
        if item == 1:
            is_all_even = False
    
    res = 0
    if is_all_even:
        if P == 0:
            res = 2 ** N
        else:
            res = 0
    else:
        res = 2**(N-1)
    
    print(res)

if __name__ == "__main__":
    resolve()

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


n,p = map(int, input().split())
a = list(map(int, input().split()))
a = [ai % 2 for ai in a]
odd, even = a.count(1), a.count(0)

ans = 0
for i in range(p,odd+1,2):
    ans += comb(odd, i) * pow(2, even)
print(ans)

Solution (Python):
from scipy.special import comb
import numpy as np

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

A = A % 2 != 0
odd = np.sum(A)
even = N - odd


ans = 0
odd_num = 0
even_num = 0
if P == 1:
    for i in range(1, odd + 1, 2):
        odd_num += comb(odd, i, exact=True)
    even_num = pow(2, even)
    ans = odd_num * even_num
else:
    for i in range(0, odd + 1, 2):
        odd_num += comb(odd, i, exact=True)
    even_num = pow(2, even)
    ans = odd_num * even_num
    
print(ans)

Solution (Python):
from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

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

def cula(a):
  ans = 0
  for i in range(a+1):
    ans+=comb(a,i)
  return ans

def culb(b):
  ans = 0
  for i in range(p,b+1,2):
    ans+=comb(b,i)
  return ans

n,p = readInts()
a = [0,0]
for i in readInts():
  if i%2==0:
    a[0]+=1
  else:
    a[1]+=1

print(cula(a[0])*culb(a[1]))

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()))





even_cnt = sum([1 for x in A if x%2 == 0])
odd_cnt = sum([1 for x in A if x%2 != 0])
if P == 0:
    ans1 = 2**even_cnt
    ans2 = 0
    for i in range(0,odd_cnt+1,2):
        ans2 += comb(odd_cnt,i)
else:
    ans1 = 2**even_cnt
    ans2 = 0
    for i in range(1,odd_cnt+1,2):
        ans2 += comb(odd_cnt,i)
print(ans1*ans2)

Solution (Python):
def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N, P = two_int()
A=many_int()

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

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

even_count=0
for i in range(even+1):
    even_count += comb(even, i)

odd_count=0
if P==1:
    for i in range(1, odd+1, 2):
        odd_count += comb(odd, i)
elif P==0:
    for i in range(2, odd+1, 2):
        odd_count += comb(odd, i)
    odd_count+=1

if odd_count != 0 and even_count != 0:
    print(odd_count * even_count)
else:
    print(odd_count)

Solution (Python):


import sys
import numpy as np
from itertools import combinations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

n_odd = 0
n_even = 0
for a in A:
    if a % 2 == 0:
        n_even += 1
    else:
        n_odd += 1

if n_even == N:
    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()))
if all(i%2==0for i in a):print(0 if p%2else 2**n)
else:print(2**(n-1))

Solution (Python):

from math import factorial
def nCr(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 i in a:
    if i % 2 == 0:
        even += 1
    else:
        odd += 1


if p == 0:
    temp = 0
    for i in range(0,odd+1,2):
        temp += nCr(odd,i)
    print(int(2**even * temp))

else:
    temp = 0
    for i in range(1,odd+1,2):
        temp += nCr(odd,i)
    print(int(2**even * temp))

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def comb(n, k):

    k = min(k, n - k)

    m = 1
    for i in range(n, n - k, -1):
        m *= i

    n = 1
    for i in range(1, k + 1):
        n *= i

    return m // n


def main():
    N, P = in_nn()
    A = in_nl()

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

    

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


def f(n, p, a):
    odd = sum(i % 2 for i in a)
    if odd == 0:
        if p == 0:
            return 2**n
        elif p == 1:
            return 0
    else:
        return 2**(n-1)
        
n, p = map(int, input().split())
a = list(map(int, input().split()))
print(f(n, p, a))

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

def nCr(n, r):
    r = min(r, n-r)

    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

x = sum(A) % 2

o = 0
e = 0

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

z = 2**e

y = 1
if P == 0:
    y = 0
if x:
    y ^= 1
res = 0
for i in range(y, o+1, 2):
    res += nCr(o, i)
    
print(res*z)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *


	
N, P = MAP()
A = LIST()

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

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

print(dp[N][P])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *


	

lim = 50  
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


	
N, P = MAP()
A = LIST()

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

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

print(dp[N][P])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *


	

lim = 50  
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


	
N, P = MAP()
A = LIST()

if any([x%2 for x in A]):
	print(pow(2, N-1))
else:
	print(pow(2, N) if P == 0 else 0)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *


	

lim = 50  
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


	
N, P = MAP()
A = LIST()

a = [x%2 for x in A]
cnt_0 = a.count(0)
cnt_1 = a.count(1)

ans = 0

for i in range(P%2, cnt_1+1, 2):
	ans += C(cnt_1, i)

ans *= pow(2, cnt_0)
print(ans)

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

fac = [1]*(n+1)
for i in range(2,n+1): fac[i] = fac[i-1]*i
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]//(fac[k]*fac[n-k])

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

cnte = cnto = 0
for i in range(even+1): cnte += comb(even,i)
for i in range(odd+1)[p::2]: cnto += comb(odd,i)
print(cnte*cnto)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *


	

lim = 50  
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod


fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


	
N, P = MAP()
A = LIST()

a = [x%2 for x in A]
cnt_0 = a.count(0)
cnt_1 = a.count(1)

ans = 2**cnt_0

if P == 0:
	c = 0
	for i in range(cnt_1//2 + 1):
		c += C(cnt_1, 2*i)
	print(ans*c)
elif P == 1:
	c = 0
	for i in range((cnt_1-1)//2 + 1):
		c += C(cnt_1, 2*i+1)
	print(ans*c)

Solution (Python):
def ncr(n, r):
    if n < r: return 0
    r = min(r, n - r)
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + i + 1 for i in range(r)]
    denominator = [i + 1 for i 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 *= numerator[k]
    return int(result)


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












dic = {'odd': 0, 'even': 0}

for i in a:
    if i % 2 == 0:
        dic['even'] += 1
    else:
        dic['odd'] += 1

even = 0
odd = 0

for i in range(dic['even'] + 1):
    even += ncr(dic['even'], i)

if p == 0:
    for i in range(0, dic['odd'] + 1, 2):
        odd += ncr(dic['odd'], i)

else:
    for i in range(1, dic['odd'] + 1, 2):
        odd += ncr(dic['odd'], i)

print(odd * even)

Solution (Python):
from math import factorial

n,p=map(int,input().split())
a=list(map(int,input().split()))
even=[]
odd=[]
for i in a:
    if i%2==0:
        even.append(i)
    else:
        odd.append(i)

ev=len(even)
od=len(odd)
odd_sum=0

for i in range(od+1):
    if i%2==p and i<=od:
        odd_sum+=(factorial(od)//(factorial(od-i)*factorial(i)))

print(odd_sum*(2**ev))

Solution (Python):
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


N, P = map(int, input().split())
A = [int(n) % 2 for n in input().split()]
cnt0 = len([a for a in A if a == 0])
cnt1 = len([a for a in A if a == 1])
ans = 0
if odd(P):
    for i in range(cnt1 + 1):
        if odd(i):
            ans += comb(cnt1, i)
else:
    for i in range(cnt1 + 1):
        if even(i):
            ans += comb(cnt1, i)
ans *= pow(2, cnt0)
print(ans)

Solution (Python):
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


if __name__ == '__main__':
    N, P = map(int, input().split())
    A = [int(n) % 2 for n in input().split()]
    cnt0 = len([a for a in A if a == 0])
    cnt1 = len([a for a in A if a == 1])
    ans = 0
    if odd(P):
        for i in range(cnt1 + 1):
            if odd(i):
                ans += comb(cnt1, i)
    else:
        for i in range(cnt1 + 1):
            if even(i):
                ans += comb(cnt1, i)
    ans *= pow(2, cnt0)
    print(ans)

Solution (Python):
import random as rng
import itertools as it
import collections as col
import heapq as hq
import sys
import copy as cp
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def dump_impl(*objects):
    print(*objects, file=sys.stderr)


def dump_dummy(*objects):
    pass


dump = dump_impl if "DEBUG" in sys.argv else dump_dummy


def odd(n): return n & 1


def even(n): return not odd(n)


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


def main():
    N, P = map(int, input().split())
    A = [int(n) % 2 for n in input().split()]
    cnt0 = len([a for a in A if a == 0])
    cnt1 = len([a for a in A if a == 1])
    ans = 0
    if odd(P):
        for i in range(cnt1 + 1):
            if odd(i):
                ans += comb(cnt1, i)
    else:
        for i in range(cnt1 + 1):
            if even(i):
                ans += comb(cnt1, i)
    ans *= pow(2, cnt0)
    print(ans)


if __name__ == '__main__':
    main()