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())
ks = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))

ans = 0
for i in range(2 ** n):
    on = [False] * n
    for j in range(n):
        if ((i>>j) & 1):
            on[n - j - 1] = True
    g = 0
    for j in range(m):
        c = 0
        for s in range(1,len(ks[j])):
            if on[ks[j][s]-1]:
                c += 1
        if c % 2 == p[j]:
            g += 1
    if g == m:
        ans += 1
print(ans)

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

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

def bitfield(n):
    return [int(digit) for digit in bin(n)[2:]]

count = 0
for i in range(1,2**N+1):
    bitarray = bitfield(i)
    bitarray.reverse()
    all_on_flg = True
    for j in range(0,M):
        num_on = sum([bitarray[k-1] if k <= len(bitarray) else 0 for k in ks[j][1:]])
        if num_on % 2 != ps[j]:
            all_on_flg = False
            break
    if all_on_flg:
        count += 1
            
print(count)

Solution (Python):


import itertools

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

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

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

switch = ('0', '1')
ans = 0
for l in itertools.product(switch, repeat=n):
    for i, kslist in enumerate(ks):
        tmp = 0
        for j in range(1, (kslist[0])+1):
            tmp += int(l[kslist[j]-1])
        if (tmp%2)!=p[i]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import product
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:] for _ in range(m)]
p = list(map(int,input().split()))
s = 0
a = 0
for i in product([0,1],repeat=n):
  for j in l:
    for k in j:
  
      a += i[k-1]
 
    if a%2!=p[l.index(j)]:
      a =0
      break
    a =0
  else:
    s += 1
print(s)

Solution (Python):
n, m = map(int, input().split())
li_swich = [[0]*n for _ in range(m)]
li_k = []
for i in range(m):
    k, *swich = map(int, input().split())
    for j in swich:
        li_swich[i][j-1] = 1
li_p = [int(x) for x in input().split()]

how_many = 0
for i in range(1<< n):
    b = True
    for k in range(len(li_swich)):
        count = 0
        li = li_swich[k]
        for j in range(len(li)):
            if (i>>j)&1:
                count += li[j]
        if count%2  != li_p[k]:
            b = False
    if b:
        how_many += 1

print(how_many)

Solution (Python):

n, m = map(int, input().split())
S = [list(map(int, input().split()))[1:] for i in range(m)]
P = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    for s, p in zip(S, P):
        c = 0
        for t in s:
            if (i >> t-1) & 1:
                c += 1
        if c % 2 != p:
            break
    else:
        ans += 1
print(ans)

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

    ans = 0
    for i in range(1<<n):
        for j in range(m):
            cnt = 0
            for b in s[j][1:]:
                if (i>>b)&1: cnt += 1
            if cnt%2 != p[j]: break
        else: ans += 1

    return ans

if __name__ == "__main__":
    print(solve())

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
def check(x):
    ok = True
    for i in range(m):
        cnt = 0
        for j in range(len(s[i])):
            if not j:continue
            if (x>> (s[i][j]-1))%2:cnt +=1
        if cnt%2 != p[i]:
            ok = False
            break
    return ok
for i  in range(2**n):
    if check(i):ans +=1
print(ans)

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

ans = 0
for i in range(2**N):
    judge = 0
    for j in range(M):
        c = 0
        for k in S[j]:
            if ((i>>(k-1)) & 1):
                c += 1
        if c % 2 != P[j]:
            judge = 1
            break
    if judge == 0:
       ans += 1

print(ans)

Solution (Python):
import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007



def main():
	
	n, m = IN()
	
	sn=[0]*n
	for i in range(m):
		dd=2 ** i
		al=list(IN())
		for ni in al[1:]:
			sn[ni-1] += dd
	
	switch_aa=list(IN())
	switch_aaa=0
	for i, v in enumerate(switch_aa):
		if v == 1:
			switch_aaa+= 2**i
	
	cc=0
	for state_i in range(2 ** n):
		switch_state=0
		for switch_i, is_on in enumerate(bin(state_i+2**12)[14-n+1:]):
			if is_on == '1':
				switch_state = switch_state ^ sn[switch_i]
		else:
			switch_state = switch_state ^ switch_aaa
			if switch_state == 0:
				cc+=1
	print(cc)
			
		
				
			
			
	
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
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 i in range(2**N):
  switch = {i:0 for i in range(1, N+1)}
  for j in range(N):
    if (i>>j)&1:
      switch[j+1] += 1    
  flag = True
  for i in range(M):
    k = ks[i][0]
    s = ks[i][1:]
    pp = p[i]
    cnt = 0
    for ss in s:
      if switch[ss] == 1:
        cnt += 1
    if cnt % 2 != pp:
      flag = False

  if flag:
    ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
k=[]
s=[]
for i in range(m):
  arr=input().split()
  k.append(int(arr[0]))
  s.append([int(arr[j+1]) for j in range(k[i])])
p=list(map(int,input().split()))
chk=[]
for i in range(1<<n):
  wk=[]
  for j in range(n):
    if 1&(i>>j)==1:
      wk.append(j+1)
  chk.append(wk)
ans=0
for i in range(len(chk)):
  calc=[0]*m
  for j in range(len(chk[i])):
    for l in range(m):
      for x in range(k[l]):
        if s[l][x]==chk[i][j]:
          calc[l]+=1
  ans+=1
  for l in range(m):
    if calc[l]%2!=p[l]:
      ans-=1
      break
print(ans)

Solution (Python):
def resolve():
    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 i in range(2**n):
        switch = [0]*n
        flag = True
        for j in range(n):
            if (i >> j) & 1:
                switch[j] = 1
        for k in range(m):
            test = ks[k][1:]
            on = 0
            for l in range(len(test)):
                if switch[test[l]-1] == 1:
                    on += 1
            if on % 2 != p[k]:
                flag = False
        if flag:
            ans += 1
    print(ans)

resolve()

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

ans = 0

for i in range(2**N):
    light = 0
    for j in range(M):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            light += 1
    if light == M:
        ans += 1

print(ans)

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


res = 0
for i in range(2**n):
    on = [0 for _ in range(n)]
    for j in range(n):
        if((i>>j)&1):
            on[j]=1
    all_on = True 
    for j in range(m):
        on_num = 0 
        for s in ks[j][1: ]:
            if(on[s-1]==1):
                on_num += 1 

        if(on_num%2 != p[j]):
            all_on = False
            break 

    if(all_on):
        res += 1
print(res)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0


for i in range(1 << N):
    for r in range(M):  
        on_sum = 0  
        for j in range(N):  
            if i >> j & 1 and j in lamps[r]:
            
                on_sum += 1  
                
        if on_sum % 2 != p[r]:  
            break  
    else:
        ans += 1
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

ans = 0


for i in range(1 << N):
    for r in range(M):  
        on_sum = 0  
        for j in range(N):  
            if i >> j & 1 and j in lamps[r]:
                on_sum += 1  
                
        if on_sum % 2 != p[r]:  
            break  
    else:
        ans += 1
print(ans)

Solution (Python):

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import itertools
N,M = map(int,readline().split())
S = [list(map(int,readline().rstrip().split()))[1:] for m in range(M)]
P = list(map(int,readline().rstrip().split()))

ans = 0
for t in itertools.product([0,1],repeat=N):
    bool = True
    for i in range(M):
        Q = sum([t[s-1] for s in S[i]])
        if (Q-P[i])%2 != 0:
            bool = False
            break
    if bool:
        ans += 1
print(ans)

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

k = [0] * M
s = [[0] * N for i in range(M)]
tmp = [0] * (N + 1)
for i in range(M):
    tmp = [int(i) for i in input().split()]
    k[i] = tmp[0]
    s[i] = tmp[1 : k[i] + 1]

p = [0] * M
p = list(map(int, input().split()))


s_cnt = [0] * M
ans = 0

for i in range(2 ** N):
    bit_str = format(i, "0"+str(N)+"b")
    s_on = True
    for j in range(len(bit_str)):
        if bit_str[j] == "1":
            for k in range(len(s)):
                if j+1 in s[k]:
                    s_cnt[k] += 1
    for j in range(len(s_cnt)):
        if s_cnt[j] % 2 != p[j]:
            s_on = False
    if s_on:
        ans += 1
    s_cnt = [0] * M

print(ans)

Solution (Python):
import itertools
n,m = map(int,input().split())
all_li = []
for _ in range(m):
    li = list(map(int,input().split()))
    li.pop(0)
    all_li.append(li)
p_li = list(map(int,input().split()))

kumi = list(itertools.product([0,1], repeat=n))






count = 0
for k in kumi:
    flag = True
    for i,each_li in enumerate(all_li):
        tmp = 0
        for e in each_li:
            if list(k)[e-1] == 1:
                tmp += 1
        if tmp%2 != p_li[i]:
            flag = False
    if flag:
        count += 1
print(count)

Solution (Python):
import time
startTimeProblem=time.time()

import fileinput, sys, itertools
from math import *
from bisect import *
from heapq import *
from collections import *

def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()



N, M = In.ints()

bulbcons = [0]*M

for i in range(M):
    bulbcons[i] = In.ints()[1::]

p = In.ints()
ans = 0



for comb in itertools.product(range(2), repeat=N):
    
    problem = False

    for i in range(M):
        res = sum([comb[bulbcons[i][j]-1] for j in range(len(bulbcons[i]))])

        if res%2 != p[i]:
            problem=True
            break
            
    if not problem:
        
        ans+=1

print(ans)




if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Solution (Python):

def main():
    n, m = map(int, input().split())
    lamps = []
    for _ in range(m):
        data = [int(i)-1 for i in input().split()][1:]
        lamps.append(data)
    p = [int(i) for i in input().split()]

    
    
    res = 0
    for i in range(1<<n):
        onSwitch = set()
        flag = True
        for j in range(n):
            if i>>j & 1:
                onSwitch.add(j)
        
        for j in range(m):
            cnt = 0
            for k in range(len(lamps[j])):
                if lamps[j][k] in onSwitch:
                    cnt += 1
            if cnt%2 != p[j]:
                flag = False
        if flag:
            res += 1 
    print(res)
main()

Solution (Python):
N,M = map(int,input().split())
S = [[int(i)-1 for i in input().split()] for _ in range(M)]
P = [int(i) for i in input().split()]

ans = 0
for i in range(1<<N):
    for j in range(M):
        cnt = 0
        for s in S[j][1:]:
            if i >> s & 1: cnt += 1
        if cnt%2 != P[j]: break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools
n, m = map(int, input().split())
s = [[0] * n for _ in range(m)]
for i in range(m):
    k, *si = map(int, input().split())
    for j in si:
        s[i][j - 1] = 1
p = list(map(int, input().split()))
l = list(itertools.product([0, 1], repeat=n))
ans = 0
for i in l:
    for index, j in enumerate(s):
        if sum([x * y for x, y in zip(i, j)]) % 2 != p[index]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
switch, light = map(int, input().split())
K = []
for _ in range(light):
    k = list(map(int, input().split()))
    K.append(k)
P = list(map(int, input().split()))

ans = 0

for i in range(2**switch):

    
    switch_on_list = [0]*light

    
    for j in range(switch):
        
        if ((i >> j) & 1):
            
            for k in range(light):
                for l in range(1, K[k][0]+1):
                    if j == K[k][l]-1:
                        switch_on_list[k] += 1

    
    for j in range(light):
        if switch_on_list[j] % 2 != P[j]:
            break
    else:
        ans += 1

print(ans)

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

ans=0
for i in range(2**n):
  num=0
  
  for j in range(m):
    cnt=0
    
    for k in range(1,l[j][0]+1):
      if (i>>l[j][k]-1) & 1:
        cnt+=1
    if cnt%2==p[j]:
      num+=1
  if num==m:
    ans+=1

print(ans)

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

ans=0
for i in range(2**n):




  
  num=0
  for j in range(m):
    
    cnt=0
    for k in range(1,l[j][0]+1):




      if (i>>l[j][k]-1)&1:
        cnt+=1

    if cnt%2==p[j]:
      num+=1
  if num==m:
    ans+=1
print(ans)

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

uoo = []

for _ in range(m):
    x = list(map(int, input().split()))
    x.pop(0)
    uoo.append(x)

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


pattern = []

for i in range(2 ** (n)):
    tmp = [0] * (n)
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    pattern.append(tmp)


ans = 0

for pat in pattern:
    is_light_up = True
    cnt = 0
    for uo in uoo:
        is_even = True
        for u in uo:
            if pat[u-1] == 1:
                is_even = not is_even
        if is_even:
            if p[cnt] == 1:
                is_light_up = False
        else:
            if p[cnt] == 0:
                is_light_up = False
        cnt += 1
    if is_light_up:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
switchss = []
for _ in range(M):
    k, *sws = map(int, input().split())
    switchss.append([sw-1 for sw in sws])
ps = list(map(int, input().split()))

ans = 0
for S in range(1<<N):
    for i in range(M):
        num = 0
        for sw in switchss[i]:
            if (S>>sw) & 1:
                num += 1
        if num%2 != ps[i]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):

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

K = []
S = []
P = []

for i in range(M):
    k,*s = map(int, input().split())
    K.append(k)
    S.append(s)
*P, = map(int, input().split())
ans = 0

for i in range(2**N):
    Switch = ["on"]*N
    flg = 0

    for j in range(N):
        if (i>>j)&1:
            Switch[j] = "off"
    for s in range(len(S)):
        count = 0
        for switch in range(len(Switch)):
            if ((switch+1) in S[s]) and Switch[switch]=="on":
                count = count + 1
        if count%2!=P[s]:
            flg = 1
            continue
    if flg==0:
        ans = ans + 1
print(ans)

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



ans=0
for i in range(2**n):
  sw=str(bin(i)).replace('b','00000000000')
  f=True
  for j in range(m):
    n_on=0
    for sj in s[j]:
      if sw[-sj]=='1':
        n_on+=1
    if n_on%2!=p[j]: 
      f=False
      break
  if f==True:
    ans+=1
    
print(ans)

Solution (Python):
def solve():
    N, M = map(int, input().split())
    K = [list(map(int, input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    
    ans = 0

    for i in range(2**N):
        s = [False] * N

        for j in range(N): 
            if 1 & (i >> j):
                s[j] = True

        for light in range(M):
            count = 0
            for switch in range(1, K[light][0]+1):
                if s[K[light][switch]-1]: 
                    count += 1
            if count &1 != P[light] &1:
                break
        else: 
            ans += 1
    print(ans)



if __name__ == '__main__':
    solve()

Solution (Python):
from itertools import accumulate, product, permutations, combinations
def solve():
    N, M = map(int, input().split())
    A = [list(map(int,input().split())) for _ in range(M)]
    P = list(map(int, input().split()))
    ans = 0
    for p in product([0,1],repeat = N):
        for i in range(M):
            xor = 0
            for j in range(1,A[i][0]+1):
                xor ^= p[A[i][j]-1]
            if xor != P[i]:
                break
        else:
            ans += 1
    return ans
print(solve())

Solution (Python):
def bitcount(x):
    r = 0
    l = len(bin(x))-2
    for i in range(l):
        if x>>i&1:r+=1
    return r
n,m = map(int,input().split())
switch = [0]*m
for i in range(m):
    tmp = list(map(int,input().split()))[1:]
    for s in tmp:
        switch[i] = switch[i]|2**(s-1)

P = list(map(int,input().split()))
ans = 0
for i in range(2**n):
    ons = 0 
    for j in range(m):
        tmp = i&switch[j]
        if bitcount(tmp)%2==P[j]:
            ons+=1
    if ons==m:ans+=1

print(ans)

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()))
cnt=0
for i in range(2**n):
    on=bin(i)[2:].zfill(n)
    for l,p in zip(L,P):
        if sum(int(on[s-1]) for s in l)%2!=p:
            break
    else:cnt+=1
print(cnt)

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

i_i = lambda: int(i_s())
i_l = lambda: list(map(int, stdin.readline().split()))
i_s = lambda: stdin.readline().rstrip()

N, M = i_l()
lamps = [[x-1 for x in i_l()[1:]] for _ in range(M)]
p = i_l()
ans = 0

for bit in range(1<<N):
    flag = True
    for i in range(M):
        cnt = 0
        for j in range(N):
            if bit & 1 << j and j in lamps[i]:
                cnt += 1
        if cnt % 2 != p[i]:
            flag = False
    if flag:
        ans += 1

print(ans)

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

cnt = 0
for i in range(2**n):
    for j in range(m):
        switch = 0
        for k in range(n):
            if (i >> k & 1) and k+1 in s[j]:
                switch += 1
        if switch % 2 != p[j]:
            break
    else:
        cnt += 1

print(cnt)

Solution (Python):
import itertools

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()))
ks = [i[0] for i in k]
ss = [i[1:] for i in k]

prods = list(itertools.product([0, 1], repeat=N))
count = 0
for prod in prods:
  check = 0
  for i in range(M):
    s = ss[i]
    
    n = sum([prod[j-1] for j in s])
    if n % 2 == p[i]:
      check += 1
  if check == M:
    count += 1
print(count)

Solution (Python):
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left 
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

N, M = map(int, input().split())
ks = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))

res = 0
for i in range(2**N):
    sw = [0]*N
    for j in range(N):  
        if ((i >> j) & 1):  
            sw[j] = 1
    
    for i, ksi in enu(ks):
        sumv = 0
        for s in ksi[1:]:
            sumv += sw[s-1]
        if sumv%2 != p[i]:
            break
    else:
        res += 1
print(res)

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

slist=[]
for i in range(M):
  k,*sl=list(map(int,input().split()))
  sw=[0]*N
  for s in sl:
    sw[s-1]=1
  slist.append(sw)
  
qlist=list(map(int,input().split()))



answer=0
for bit in itertools.product(range(2),repeat=N):
  for i in range(M):
    parity=0
    for j in range(N):
      parity+=slist[i][j]&bit[j]
    if qlist[i]!=parity%2:
      break
  else:
    answer+=1
    
print(answer)

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

S = []
for _ in range(M):
    K = list(map(int, input().split()))
    S.append(K[1:])

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

ans = 0
for i in range(2 ** N):
    on_switch = []
    for j in range(N):
        if ((i >> j) & 1):
            on_switch.append(j + 1)
    clear = True
    for k, s in enumerate(S):
        res = 0
        for si in s:
            if si in on_switch:
                res += 1
        if res % 2 != P[k]:
            clear = False
            break
    if clear:
        ans += 1

print(ans)

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

x = []
for i in range(2**n):
    temp = []
    for j in range(n):
        if i>>j & 1:
            temp.append(j+1)
    x.append(temp)

l = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))

z = 0
for a in range(2**n):
    for b in range(m):
        y = 0
        for c in range(l[b][0]):
            if l[b][c+1] in x[a]:
                y += 1
        if y % 2 != p[b]:
            break
    else:
        z += 1

print(z)

Solution (Python):

import io

n,m = map(int,input().split())
S = []
for _ in range(m):
  s = list(map(int,input().split()))
  del s[0]
  k = 0
  for i in s:
    k +=  1<<(i-1)
  S.append(k)

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

qwe = [[] for _ in range(m+1)]
qwe[0] = [i for i in range(2**n)]
for i in range(m):
  for j in qwe[i]:
    if str(bin(j & S[i])).count('1')%2==p[i]:
      qwe[i+1].append(j)
      
print(len(qwe[m]))

Solution (Python):
from itertools import product
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M = map(int, readline().split())
    S = [[int(i) for i in readline().split()] for _ in range(M)]
    P = [int(i) for i in readline().split()]

    ans = 0
    A = [[0, 1] for _ in range(N)]
    for pattern in product(*A):
        on = []
        for s in S:
            tmp = 0
            for i in range(s[0]):
                tmp += pattern[s[i+1]-1]
            on.append(tmp % 2)

        if on == P:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0
pattern = [0]*N

def dfs(pattern, pos):
    if pos == N:
        for i in range(M):
            num , *switches = ks[i]
            if sum([pattern[sw-1] for sw in switches]) % 2 != P[i]:
                break
        else:
            global cnt
            cnt += 1
    else:
        pattern[pos] = 0
        dfs(pattern, pos+1)
        pattern[pos] = 1
        dfs(pattern, pos+1)
        
dfs(pattern, 0)
print(cnt)

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

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

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

ans = 0
for j in range(2**n):
    tmp_sw = bin(j)[2:].zfill(n)
    

    break_on = 0
    for k in range(m):
        tmp = 0
        
        for h in s[k]:
            if tmp_sw[h-1] == '1':
                tmp += 1
        
        if tmp % 2 != p[k]:
            break_on = 1
    
    if break_on == 0:
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




from itertools import product

N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0


    
    
for l in product([0, 1], repeat=N):
    for i in range(M):
        num , *switchs = ks[i]
        if sum([l[sw-1] for sw in switchs]) % 2 != P[i]:
            break
    else:
        cnt += 1

print(cnt)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N, M = mi()
ks = []
for i in range(M):
    a = li()
    ks.append(a)
P = li()

cnt = 0
for i in range(2**N):
    x = bin(i)[2:].zfill(N)
    l = list(map(int, list(x)))
    flag = 1
    for i in range(M):
        num , *switchs = ks[i]
        if sum([l[sw-1] for sw in switchs]) % 2 != P[i]:
            flag = 0
            break
    if flag:
        cnt += 1

print(cnt)

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

for i in range(2**n):
    bulb = [0]*m
    bin_str = format(i, '010b')
    for j in range(m):
        cnt = 0
        for k in ks[j][1:]:
            
            if bin_str[-k] == "1":
               cnt += 1 
        if cnt % 2 == p[j]:
            
            bulb[j] = 1
    
    
    if bulb == [1]*m:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
K = []
for i in range(M):
    S = list(map(int,input().split()))
    k,s = S[0],S[1:]
    K.append(s)
P = list(map(int,input().split()))

ans = 0
for i in range(pow(2,N)):
    Sw = []
    n = i
    for j in range(N):
        Sw.append(n%2)
        n//=2
    A = 0
    for k in range(M):
        n = 0
        for j in K[k]:
            n+=Sw[j-1]
        if n%2==P[k]:
            A+=1
    if A==M:ans += 1
print(ans)

Solution (Python):
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 i in range(2**n):
    on = [0 for _ in range(n)]
    
    for j in range(n):
        if ((i>>j)&1):
            on[j] = 1
    all_on = True
    for j in range(m):
        on_num = 0
        for s in ks[j][1:]:
            if on[s-1]==1:
                on_num = on_num + 1
                
        if on_num%2 != p[j]:
            all_on = False
            break
    if all_on:
        ans = ans+1
print(ans)