Problem: 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?

Submission attempts (in order):
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



mod = 10**9+7 
N = 10**5
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(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)



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


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)



Verdicts: Wrong Answer

Accepted