Problem:
 Score : 300 points    Problem Statement We have N switches with "on" and "off" state, and M bulbs. The switches are numbered 1 to N , and the bulbs are numbered 1 to M .  Bulb i is connected to k_i switches: Switch s_{i1} , s_{i2} , ... , and s_{ik_i} . It is lighted when the number of switches that are "on" among these switches is congruent to p_i modulo 2 .  How many combinations of "on" and "off" states of the switches light all the bulbs?      Constraints  1 \leq N, M \leq 10  1 \leq k_i \leq N  1 \leq s_{ij} \leq N  s_{ia} \neq s_{ib} (a \neq b)  p_i is 0 or 1 .  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  M  k_1  s_{11}  s_{12}  ...  s_{1k_1}  :  k_M  s_{M1}  s_{M2}  ...  s_{Mk_M}  p_1  p_2  ...  p_M       Output Print the number of combinations of "on" and "off" states of the switches that light all the bulbs.        Sample Input 1 2 2
2 1 2
1 2
0 1      Sample Output 1 1   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   There are four possible combinations of states of (Switch 1 , Switch 2 ): (on, on), (on, off), (off, on) and (off, off). Among them, only (on, on) lights all the bulbs, so we should print 1 .       Sample Input 2 2 3
2 1 2
1 1
1 2
0 0 1      Sample Output 2 0   Bulb 1 is lighted when there is an even number of switches that are "on" among the following: Switch 1 and 2 .  Bulb 2 is lighted when there is an even number of switches that are "on" among the following: Switch 1 .  Bulb 3 is lighted when there is an odd number of switches that are "on" among the following: Switch 2 .   Switch 1 has to be "off" to light Bulb 2 and Switch 2 has to be "on" to light Bulb 3 , but then Bulb 1 will not be lighted. Thus, there are no combinations of states of the switches that light all the bulbs, so we should print 0 .       Sample Input 3 5 2
3 1 2 5
2 2 3
1 0      Sample Output 3 8

Solution (Python):
N, M = map(int, input().split())
s = []
for i in range(M):
    s.append(list(map(int, input().split())))
p = list(map(int, input().split()))

switch = [['0'], ['1']]

for i in range(N-1):
    tmp = []
    for j in switch:
        tmp.append(j+['0'])
        tmp.append(j+['1'])
    switch = tmp 

ans = 0

for i in switch:
    false = 0
    for j in range(M):
        cnt = 0 
        for k in range(s[j][0]):
            if i[s[j][1+k]-1] == '1':
                cnt += 1
        if cnt%2 != p[j]:
            false += 1 
    if false == 0:
        ans += 1 
print(ans)

Solution (Python):
import numpy as np
import itertools

N, M = map(int, input().split())
switch = [[] for _ in range(M)]
for i in range(M):
    switch[i] = list(map(lambda x: int(x)-1, input().split()[1:]))
p = list(map(int, input().split()))

bit = itertools.product(range(2), repeat=N)
cnt = 0
for b in bit:
    np_b = np.array(b)
    on = 1
    for bulb in range(M):
        on *= sum(np_b[switch[bulb]]) % 2 == p[bulb]
    cnt += on
print(cnt)

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

ks = []
ss = []
for i in range(m):
    s = list(map(int, input().split()))
    k = s.pop(0)
    ks.append(k)
    ss.append(s)

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

import itertools
combs = itertools.product([1, 0], repeat=n)

res = 0
for comb in combs:
    valid = True
    for i in range(m):
        p = ps[i]
        k = ks[i]
        s = ss[i]
        cnt = 0
        for j in range(k):
            cnt += comb[s[j] - 1]
        if cnt % 2 != p:
            valid = False
            break
    if valid:
        res += 1

print(res)

Solution (Python):
import numpy as np
N, M = map(int, input().split())


s=np.zeros((M,N))
for i in range(M):
    ks = list(map(int, input().split()))  
    for j in range(ks[0]):
        s[i, ks[j+1]-1]=1
P = list(map(int, input().split()))      
    
counter=0

for k in range(2**N):
    k_bit = list(map(int, list(np.binary_repr(k, N))))
    
    b_status = np.dot(s, k_bit)%2
    
    if all(b_status==P)==True:
        counter +=1

print(counter)

Solution (Python):
import numpy as np

N, M=map(int, input().split())
matrix=np.zeros((M, N))

for i in range(M):
  temp=np.array(list(map(int, input().split())))
  temp-=1
  matrix[i, temp[1:]]=1
  
p=np.array(list(map(int, input().split())))

counter=0
for i in range(pow(2, N)):
  s=np.array(list(map(int, list(format(i, '0'+str(N)+'b')))))
  if all(np.dot(matrix, s)%2==p)==True:
    counter+=1
    
print(counter)

Solution (Python):
n,m=map(int,input().split())
s=[]
for i in range(m):
    s.append(list(map(int,input().split())))
p=list(map(int,input().split()))

onoff=[["0"],["1"]]

for i in range(n-1):
    tmp=[]
    for j in onoff:
        tmp.append(j+["0"])
        tmp.append(j+["1"])
    onoff=tmp

ans=0
for i in onoff:
    f=0
    for j in range(m):
        c=0
        for k in range(s[j][0]):
            if i[s[j][1+k]-1]=='1':
                c+=1
        if c%2!=p[j]:
            f+=1
    if f==0:
        ans+=1
print(ans)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
lst = [LI() for _ in range(m)]
p = LI()
ans = 0
for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if (i>>j) & 1:
            switch[j] = 1
    for j in range(m):
        k = lst[j][0]
        tmp = 0
        for l in range(k):
            if switch[lst[j][l+1]-1] == 1:
                tmp += 1
        if tmp % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
bulbs = []
for _ in range(M):
    b = tuple(map(int, input().split()))
    bulbs.append(b[1:])
p = list(map(int, input().split()))    

ans = 0
for switch in range(2**N):
    check = [0] * M
    for i, bulb in enumerate(bulbs):
        cnt = 0
        for b in bulb:
            if switch >> (b-1) & 1:
                cnt += 1
                
        if cnt % 2 == p[i]:
            check[i] = True
        else:
            check[i] = False
        
    if all(check):
        ans += 1

print(ans)

Solution (Python):

n,m = map(int,input().split())
res = 0

q = []
for i in range(m):
    q.append(list(map(int,input().split())))
p = list(map(int,input().split()))


for s in range(2**n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1,len(q[i])):
            w = q[i][j]
            if s>>(w-1) &1 == 1: 
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Solution (Python):
n, m = map(int, input().split())
l = [list(map(int, input().split())) [1:] for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
on_off = [[0], [1]]

for _ in range(n-1):
  tmp = []
  for j in on_off:
    tmp.append(j+[0])
    tmp.append(j+[1])
  on_off = tmp

for x in on_off:
  cnt = 0
  for y in range(m):
    z = 0
    for c in l[y-1]:
      z += x[c-1]
    if z%2 == p[y-1]%2:
      cnt += 1
  if cnt == m:
    ans += 1
print(ans)

Solution (Python):

n,m = map(int, input().split())
cond = []
for i in range(m):
  temp = input().split()
  cond.append([int(i) for i in temp])
p = [int(i) for i in input().split()]

ans = 0
for i in range(2**n): 
  flag = True
  temp = bin(i)
  sw = [str(l) for l in temp]
  sw.reverse()
  flag = True
  for j in range(m): 
    if flag:
      c = 0 
      for k in range(1,len(temp)-1): 
        if cond[j][1:].count(k)==1:
          c += int(sw[k-1])
      if c%2 != p[j]: 
        flag = False
      elif c%2 == p[j] and j==m-1: 
        ans += 1
        
print(ans)

Solution (Python):


N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0

for b in range(1<<N):
    for i in range(M):
        c = 0
        for s in src[i][1:]:
            
            if b&(1<<(s-1)):
                c += 1
        
        
        if c%2 != P[i]: break
    else:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
k_s = list(list(int(i) for i in input().split()) for i in range(m))
p = list(map(int, input().split()))

ans = 0
temp1 = 0
temp2 = 0

for i in range(2 ** n):
    num = bin(i)
    num2 = num.lstrip('0b')
    num3 = num2.zfill(n)
    
    for j in range(m):
        for l in range(k_s[j][0]):
            temp1 += int(num3[k_s[j][l + 1] - 1])
        if temp1 % 2 == p[j]:
            temp2 += 1
            temp1 = 0
        else:
            temp1 =0
    
    if temp2 == m:
        ans += 1
    temp2 = 0
    
print(ans)

Solution (Python):










N, M = map(int, input().split())  

connect_infos = []

for i in range(M):
    k, *S = list(map(lambda x: int(x)-1, input().split()))
    connect_infos.append(S)



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



switches_status = [[] for _ in range(1 << N)]

for mask in range((1 << N)):  
    for i in range(N):
        switches_status[mask].append((mask >> i) & 1)



ans = 0

for status in switches_status:
    shine = 0
    
    for i, connect_info in enumerate(connect_infos):
        
        on_count = 0
        for j in connect_info:
            on_count += status[j]
        
        if on_count % 2 == P[i]:
            shine += 1
    if shine == M:  
        ans += 1

print(ans)

Solution (Python):










N, M = map(int, input().split())  

connect_infos = []

for i in range(M):
    k, *S = list(map(lambda x: int(x)-1, input().split()))
    connect_infos.append(S)



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



switches_status = [[] for _ in range(1 << N)]

for mask in range((1 << N)):  
    for i in range(N):
        switches_status[mask].append((mask >> i) & 1)



ans = 0

for status in switches_status:
    shine = 0
    
    for i, connect_info in enumerate(connect_infos):
        
        on_count = 0
        for j in connect_info:
            on_count += status[j]
        
        if on_count % 2 == P[i]:
            shine += 1
    if shine == M:  
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)

N, M = map(int, input().split())

lightBulbs = [None]*M
for i in range(M):
    data = list(map(int, input().split()))
    lightBulbs[i] = data[1:]

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

def rec(pos, count, status):
    if pos == N:
        count += judge(status)
        return count
    status[pos] = 0
    count = rec(pos+1, count, status)
    status[pos] = 1
    count = rec(pos+1, count, status)
    return count

def judge(status):
    for i, lightBulb in enumerate(lightBulbs):
        toggle = 0
        for switch in lightBulb:
            toggle += status[switch-1]
        toggle %= 2
        if P[i] != toggle:
            return 0
    return 1 
    

ans = rec(0, 0, [0]*N)
print(ans)

Solution (Python):
import math
import copy
import fractions
import numpy as np



def getInputNum():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList



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

status = getSomeInputListInt(m)
condition = getInputListInt()

ans = 0
mask = []

for i in range(len(status)):
    mask.append(0b0)
    for j in range(1, status[i][0]+1):
        tmp = 1
        tmp = tmp << (status[i][j] - 1)
        mask[i] = mask[i] | tmp

for i in range(2**n):
    flg = True
    for j in range(m):
        masked = i & mask[j]
        oneCnt = bin(masked).count("1")
        if oneCnt % 2 != condition[j]:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
Switch = [0] * N
for i in range(M):
  k,*S = map(int,input().split())
  for s in S:
    s -= 1
    Switch[s] |= (1 <<i)

P = list(map(int,input().split()))
p = 0
for i in range(M):
  p |= (P[i] <<i)


ans = 0
for i in range(2 ** N):
  light = 0
  for j in range(N):
    if (i >>j) & 1 == 1:
      light ^= Switch[j]
  if light == p:
    ans += 1
print(ans)

Solution (Python):


def f(X, Y):
    return(len(X.intersection(Y)) % 2)

n, m = [int(el) for el in input().split(' ')]


T = []
for i in range(m):
    S = set()
    tmp = [int(el) for el in input().split(' ')]
    for j in range(1, len(tmp)):
        S.add(tmp[j])
    T.append(S)
P = [int(el) for el in input().split(' ')]



total = 0
for i in range(2**n):
    pattern = set()
    for j in range(n):
        if ((i >> j) & 1):
            pattern.add(j+1)
    
    if all([P[k] == f(T[k], pattern) for k in range(m)]):
        total += 1
print(total)

Solution (Python):
N,M = [int(s) for s in input().split()]
light=[0 for i in range(M)]
for i in range(M):
  lst= [int(s) for s in input().split()]
  light[i]=lst
mod= [int(s) for s in input().split()]
swi=[[]]
for i in range(N):
  p0=[s+[0] for s in swi]
  p1=[s+[1] for s in swi]
  swi=p0+p1
count=0
for i in range(2**N):
  flag=1
  for j in range(M):
    k=light[j][0]
    add=0
    for l in range(1,k+1):
      add=add+swi[i][light[j][l]-1]
    if(add%2!=mod[j]):
      flag=0
      break
  count=count+flag
print(count)

Solution (Python):


from itertools import product

n, m = list(map(int, input().split()))
k_list = []
s_list_list = []

for _ in range(m):
    k, *s = list(map(int, input().split()))
    k_list.append(k)
    s_list_list.append(s)

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


s_p_list = product([0, 1], repeat=n)
c = 0
match_list = []
for s_p in s_p_list:

    is_match = True
    for i, s_list in enumerate(s_list_list):
        w = sum([s_p[s-1] for s in s_list])
        if w % 2 != p_list[i]:
            is_match = False
            break
    if is_match:
        c += 1
        match_list.append(s_p)

print(c)

Solution (Python):
from collections import defaultdict

dic = defaultdict(list)
n, m = map(int, (input()).split())

for i in range(1, m+1):
    k, *to_swi = map(int, input().split())
    if k == 1:
        list(to_swi)
    for swi in to_swi:
        dic[swi].append(i)

P = [0] + list(map(int, input().split()))
count = 0
for i in range(2**n):
    rights = [0] * (m + 1)
    for j in range(n):
        if (i >> j) & 1:
            for right in dic[j+1]:
                rights[right] += 1
                rights[right] %= 2

    if rights == P:
        count += 1

print(count)

Solution (Python):
import itertools

N, M = map(int, input().split())
s = [list(map(int, input().split())) for i in range(M)]
k = [s[i].pop(0) for i in range(M)]
p = list(map(int, input().split()))


c = list(itertools.product(range(2), repeat = N))


def l(x, y):
    switch_on = 0
    for i in range(k[x]):
        switch_on += c[y][s[x][i] - 1]
    if switch_on % 2 == p[x]:
        return 1
    else:
        return 0

ans = 0
for j in range(2 ** N):
    light_on = 0
    for i in range(M):
        light_on += l(i, j)
    if light_on == M:
        ans += 1
    else:
        pass

print(ans)

Solution (Python):
import sys

"""


    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""



if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().split())
    L = [list(map(int,list(sys.stdin.readline().split()))) for i in range(M)]
    cond = list(map(int, sys.stdin.readline().split()))

    cnt = 0
    for sw_bit in range(1 << N):
        flag = True
        for l, c in zip(L, cond):
            bit = 0
            for e in l[1::]:
                bit |= (1 << (e - 1))
            
            bit &= sw_bit
            if bin(bit).count("1") % 2 != c:
                flag = False
                break
        if flag:
            cnt += 1
    print(cnt)

Solution (Python):
n,m = map(int,input().split())
s = [list(map(int,input().split()[1:])) for _ in range(m)]
p = list(map(int,input().split()))

ans = 0

for i in range(2**n):
    f = 1
    for j in range(m):
        g = 1
        g &= (sum([int(bin(i>>(u-1)),2) for u in s[j]])%2 == p[j])
        f &= g
    ans += f
print(ans)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
s = [None for _ in range(m)]

for i in range(m):
    s[i] = list(map(int, input().split()))

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

ans = 0
for tpl in product([0, 1], repeat=n):
    for i in range(m):
        cnt = 0
        is_on = True
        for j in range(s[i][0]):
            if tpl[s[i][j + 1] - 1] == 1:
                cnt += 1
        if cnt % 2 != p[i]:
            is_on = False
            break
    if is_on:
        ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
d={}
for i in range(M):
    a,*b=map(int,input().split())
    d[i]=b
p=list(map(int,input().split()))
cnt=0
for i in range(2**N):
    t=bin(i)[2:]
    t='0'*(N-len(t)+1)+t
    t=list(t)
    f=True
    for j in range(M):
        s=0
        for k in d[j]:
            s+=int(t[k])
        if s%2!=p[j]:
            f=False
            break
    if f:cnt+=1
print(cnt)

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

def main(): 
    N,M = map(int,input().split())
    ks=[list(map(int, input().split())) for _ in range(M)]
    p = list(map(int, input().split()))
    ans = 0
    for bit in range(2**N):
        Flag = True
        for i in range(M):
            count = 0
            for j in range(1,ks[i][0]+1):
                if bit & (1<<ks[i][j]-1):
                    count += 1
            if count%2!=p[i]:
                Flag = False
                break
        if Flag:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product


def main():
    N, M = map(int, input().split())
    conn = [
        list(map(int, input().split()[1:]))
        for _ in range(M)
    ]
    conds = list(map(int, input().split()))

    print(len([
        state
        for state in product(("ON", "OFF"), repeat=N)
        if all(
            len([s for s in switches if state[s - 1] == "ON"]) % 2 == p
            for switches, p in zip(conn, conds)
        )
    ]))


if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product


def main():
    N, M = map(int, input().split())
    conn = [
        list(map(int, input().split()[1:]))
        for _ in range(M)
    ]
    conds = list(map(int, input().split()))

    ans = 0
    for state in product(("ON", "OFF"), repeat=N):
        if all(
            len([s for s in switches if state[s - 1] == "ON"]) % 2 == p
            for switches, p in zip(conn, conds)
        ):
            ans += 1
            
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from numpy import*
n,m=map(int,input().split())
l=[]
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())
 
ans=0
for t in range(2**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)

Solution (Python):
N, M = map(int,input().split())
K = [list(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

switch_sum = 0
switch_ptn = 0
switch_ptn2 = 0


for i in range(2**N):
  i_2 = str(bin(i))[2:]
  i_bit = i_2.zfill(N)
  
  

  for j in range(M):
    for k in range(1,K[j][0]+1):
      switch_sum += int(i_bit[K[j][k]-1])
    switch_sum = switch_sum%2

    if switch_sum == P[j]:
      switch_ptn += 1
    switch_sum = 0
  if switch_ptn == M:
    switch_ptn2 += 1
  switch_ptn = 0
    
print(switch_ptn2)

Solution (Python):
n, m = [int(x) for x in input().split(' ')]
s = [[int(x) for x in input().split(' ')[1:]] for _ in range(m)]
p = input().split(' ')

cnt = 0
for i in range(0, 2**n):
    ptn = '0'+format(i, '010b')[::-1]
    light = []
    for j, sw in enumerate(s):
        on_sws = [ptn[sw_i] for sw_i in sw if ptn[sw_i] == '1']
        light.append(len(on_sws) % 2 == int(p[j]))
    if all(light):
        cnt += 1

print(cnt)

Solution (Python):

N,M = map(int, input().split())

l1 = [0]*M;
for i in range(M):
  l1[i] = list(map(int, input().split()))

l2 = list(map(int,input().split()))
anser = 0

for i in range(2**N):
  isAll = True
  switch = '{:010b}'.format(i)
  
  for j in range(M):
    
    
    count = 0
    
    for k in range(l1[j][0]):
      
      
      div = l1[j][k+1]-1
      if int(switch[9-div:10-div]) == 1:
        count += 1
    if count%2 != l2[j]:
      isAll = False
      break
  if isAll:
    anser += 1
print(anser)

Solution (Python):
n, m = map(int,input().split())
depends = []
for i in range(m):
    depends.append([ int(i)-1 for i in input().split() ])
p = [ int(i) for i in input().split() ]
ans = 0
for i in range(2**n):
    chosen = set()
    for j in range(n):
        if i & (1<<j):
            chosen.add(j)
    
    ok = 0
    for j in range(m):
        
        req = p[j]
        cnt = 0
        for k in range(1,depends[j][0]+2):
            if depends[j][k] in chosen:
                cnt += 1
        if cnt % 2 == req:
            ok += 1

    if ok == m:
        ans += 1
print(ans)

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

def main():
    N,M=map(int, input().split())

    K=[]
    for i in range(M):
        sw = list(map(int, input().split()))
        x = 0
        for j in sw[1:]:
            x += 2**(j-1)
        K.append(x)

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

    ans = 0
    for i in range(2**N):
        b = True
        for j in range(M):
            if "{:b}".format(i&K[j]).count("1") %2 != P[j]:
                b = False
                break
        if b:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

def main():
    N,M=map(int, input().split())
    K=[]
    for i in range(M):
        K.append(list(map(int, input().split())))
    P = list(map(int, input().split()))

    ans = 0
    for i in range(2**N):
        s = "{:0" + str(N) +"b}"
        b = True
        for j in range(M):
            x = 0
            for k in K[j][1:]:
                x += int(2**(N-k))
            s = "{:b}".format(i&x)
            if s.count("1")%2 != P[j]:
                b = False
                break
        if b:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M = map(int, input().split())
A = []
for _ in range(M):
    B = list(map(int, input().split()))
    A.append(B)
P = list(map(int, input().split()))
answer = 0

for i in range(2**N):
    p = [0]*N
    tmp = i
    for j in range(N):
        if tmp%2 == 1:
            p[j] = 1
        tmp //= 2
    flag = 0
    for j in range(M):
        count = 0
        for k in range(len(A[j])-1):
            if p[A[j][k+1]-1] == 1:
                count += 1
        if not count%2 == P[j]:
            flag = 1
    if flag == 0:
        answer += 1
    
print(answer)

Solution (Python):
from functools import reduce
import math

N, M = [int(a) for a in input().split()]
s = []
bulb_list = []

for i in range(M):
  line = [int(a) for a in input().split()]
  k = line[0]
  s.append([int(x) for x in line[1:k+1]])
  bulb_list += s[i]


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

count = 0

for i in range(int(math.pow(2, N))):
  onoff = format(i, '010b')
  ok = True
  
  
  for j in range(M):
    l = list(map(lambda x: int(onoff[-x]), s[j]))
    mod = reduce(lambda a, b: a+b, l) % 2
    
    if mod != p[j]:
      ok = False
      break
  if ok:
    
    count += 1

print(count)

Solution (Python):
N, M = map(int,input().split())
s = [list(map(int,input().split())) for i in range(M)]
p = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    switch = format(i, '010b')
    switch = switch[-N:]
    cn = 0
    for j in range(M):
        t = s[j]
        count = 0
        for k in t[1:]:
            if int(switch[k-1]) == 1:
                count += 1
        if count % 2 == p[j]:
            cn += 1
    if cn == M:
        ans += 1
print(ans)

Solution (Python):
import itertools

N,M = map(int,input().split())

sw = [[] for _ in range(M)]
for i in range(M):
    sw[i] = list(map(int,input().split()[1:]))

P = list(map(int,input().split()))
ans = 0
for tpl in itertools.product([0,1], repeat=N):
    bl = True
    for i in range(M):
        s = sum([tpl[j-1] for j in sw[i]])
        if (s-P[i])%2 == 1:
            bl = False
            break
    if bl:
        ans += 1

print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    switches = []
    for _ in range(M):
        tp = list(map(int, input().split()))
        temp = [int(x) for x in tp[1:]]
        switches.append(temp)

    P = [int(p) for p in input().split()]
    d = dict()
    for i in range(M):
        for j in range(len(switches[i])):
            sw = switches[i][j]
            if sw not in d: d[sw] = [i]
            else: d[sw].append(i)

    states = dict()
    
    ground = tuple([(P[i]+1) % 2 for i in range(M)])
    states[ground] = 1
    for sw in range(1, N+1):
        if sw in d:
            new = dict()
            for s in states:
                st = list(s)
                for j in d[sw]:
                    st[j] = (st[j]+1) % 2
                st = tuple(st)
                new[st] = new.get(st, 0) + states[s]
            for st in new:
                states[st] = states.get(st, 0) + new[st]
        else:
            for s in states:
                states[s] *= 2
        
    
    final = tuple([1 for _ in range(M)])
    return states.get(final, 0)


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

Solution (Python):
from itertools import product

n, m = map(int, input().split())
ksskss = [list(map(int, input().split())) for _ in range(m)]
pp = list(map(int, input().split()))

switches = [(0, 1) for _ in range(n)]
ans = 0
for state in product(*switches) :
    bulbs = [0 for _ in range(m)]
    for i, ((_, *ss), p) in enumerate(zip(ksskss, pp)) :
        p ^= 1
        for s in ss :
            if state[s-1] :
                p ^= 1
        if p :
            bulbs[i] = 1
    if all(bulbs) :
        ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
switches=[]
for i in range(M):
  switch=list(map(int,input().split()))
  switch=switch[1:]
  switches.append(switch)
P=list(map(int,input().split()))
ans=0
def check_d(bottun):
  for i in range(M):
    b_c=0
    for j in switches[i]:
      if (bottun>>(j-1)) & 1 == 1:
        b_c+=1
    if b_c%2!=P[i]:
      return 0
  return 1
    
for bottun in range(2**N):
  ans+=check_d(bottun)
print(ans)

Solution (Python):
n, m = map(int, input().split())
switch = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for bits in range(1<<n):
    all_on = True
    for i in range(m):
        pow = 0
        for j in range(1, switch[i][0]+1):
            pow += (bits >> (switch[i][j]-1)) & 1
        if pow % 2 != p[i]:
            all_on = False
            break

    if all_on:
        
        ans += 1

print(ans)

Solution (Python):
from itertools import combinations as combi
N, M = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
def check(s):
  for i in range(M):
    temp = 0
    for j in range(1, S[i][0] + 1):
      if S[i][j] in s:
        temp += 1
    if temp % 2 != p[i]:
      return False
  return True
res = 0
for i in range(0, N + 1):
  for com in combi(range(1, N + 1), i):
    if check(set(com)) == True:
      res += 1
print(res)

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

x = 2 ** N

ks = []
for i in range(M):
    ks.append(list(map(int,input().split())))

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

ans = 0

for i in range(x):
    str_i = str(bin(i))[2:].zfill(N)
    flag = True
    for j in range(M):
        ks_j = ks[j]
        on_sum = 0
        for k in range(ks_j[0]):
            if(str_i[ks_j[k+1]-1] == '1'):
                on_sum += 1
        if(on_sum % 2 != p[j]):
            flag = False
            break
    if(flag):
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
p_lst = list(map(int, (input().split())))

res = 0
for i in range(2**n):
    format_string = '0' + str(n) + 'b'
    i_str = format(i, format_string)
    for k, lamp in enumerate(lst):
        count = 0
        r = p_lst[k]
        for switch in lamp[1:]:
            count += int(i_str[switch-1])
        if r != count % 2:
            
            break
    else:
        
        res += 1
print(res)

Solution (Python):
ans=0
n,m=map(int,input().split())
l1=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
for i in range(2**n):
    a=[]
    for j in range(n):
        if i>>j&1:
            a.append(j+1)
    for j in range(m):
        if len(set(a)&set(l1[j][1:]))%2==p[j]:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
KS = [[] for i in range(M)]
for i in range(M):
  KS[i]= list(map(int, input().split()))
P = list(map(int, input().split()))

ans = 0
for i in range(2**N):
  sl = []
  for j in range(N):
    if (i>>j)&1:
      sl.append(j+1)
  for j in range(M):
    if len(set(KS[j][1:])&set(sl))%2 ==P[j]:
      continue
    else:
      break
  else:
    ans += 1
    
print(ans)

Solution (Python):

N, M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0


for b in range(1<<N):  
    
    for i in range(M):
        c = 0

        
        for s in src[i][1:]:
            
            
            switch_num = s-1

            

            if (b >> switch_num) & 1 == 1:
                c += 1

        if c%2 != P[i]:
            break
    else:
        
        ans += 1

print(ans)

Solution (Python):
n, m = (int(i) for i in input().split())
swi = [[int(i) for i in input().split()[1:]] for _ in range(m)]
p = [int(i) for i in input().split()]

ans = 0
bits = [0]*n
for switch_state in range(2**n):
    swi_bin = str(bin(switch_state))
    for i in range(n):
        bits[i] = int(swi_bin[-1-i] if i < len(swi_bin) and swi_bin[-1-i] != 'b' else 0)
    for i in range(m):
        cnt_on = 0
        for s in swi[i]:
            cnt_on += bits[s-1]
        if cnt_on%2 != p[i]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    temp = list(map(int, input().split()))
    K.append(temp[0])
    S.append(temp[1:len(temp)])
p = list(map(int, input().split()))

L = list(itertools.product([0,1], repeat=N))
ans=0
for l in L:
    i=0
    ans_count = 1
    for s in S:
        c=0
        for j in range(K[i]):
            c += l[s[j]-1]
        if c%2!=p[i]:
            ans_count=0
        i+=1
    ans+=ans_count
print(ans)