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):
import math

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

cnt = 0
for i in range(int(math.pow(2,n))):
    isall_lighted = True
    bin = i
    onoff = [0]*n
    for i in range(n):
        digit = int(math.pow(2, i+1))
        if bin % digit != 0:
            onoff[i] = 1
            bin = bin - digit//2

    for i, light in enumerate(s):
        sw_cnt = 0
        for sw in light:
            sw_cnt += onoff[sw-1]
        if sw_cnt % 2 != p[i]:
            isall_lighted = False
    if isall_lighted:
        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()))

allbit = []
for i in range(2**N):
  bit = [0] * N
  for j in range(N):
    if (i >> j) & 1:
      bit[j] = 1
  allbit.append(bit)


j=0
for onof in allbit:
    l=0
    for m in range(M):
        s=ks[m][1:]
        i=0
        for st in s:
            i+=onof[st-1]
        if(i%2==p[m]):
            l+=1
    if(l==M):
        j+=1
        
print(j)

Solution (Python):
n,m=map(int,input().split())
s=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
num = 0
for i in range(2**n):
    onof = format(i,'b').zfill(n)
    for j in range(m):
        sum_onof = 0
        for k in range(s[j][0]):
            sum_onof += int(onof[s[j][k+1]-1])
        if sum_onof%2 != p[j]:
            break
        elif j == m-1:
            num += 1
print(num)

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

ans = 0
for i in range(2**N):
    f = True
    for s, p in zip(S, P):
        c = 0
        for k in s:
            if i & 1 << k == 1 << k:
                c += 1
        if(c % 2 != p):
            f = False
            break
    if f:
        ans += 1
print(ans)

Solution (Python):
def solve(n, m, k, s, p):
    switch_sockes_mapping = {i: [] for i in range(n)}
    for i in range(m):
        for switch in s[i]:
            switch -= 1
            switch_sockes_mapping[switch].append(i)

    res = 0
    for mask in range(2**n):
        nums = [0] * m 
        for i in range(n):
            if (2**i) & mask:
                for j in switch_sockes_mapping[i]:
                    nums[j] += 1
        cnt = 0
        for j in range(m):
            if nums[j] % 2 == p[j]:
                cnt += 1
        if cnt == m:
            res += 1
    return res

n, m = map(int, input().split())
k = [0] * m
s = []
for i in range(m):
    v = list(map(int, input().split()))
    k[i] = v[0]
    s.append(v[1:])
p = list(map(int, input().split()))
print(solve(n, m, k, s, p))

Solution (Python):
import numpy as np
n,m = map(int, input().split())
sl= [[0]]*m
for i in range(m):
    k,*s = map(int,input().split())
    sl[i] =list(map(lambda x: 10-x+1 , s))
pl = list(map(int,input().split()))

cnt = 0

for j in range(2**n):
    switch = np.array(list(map(int,list(format(j, '011b')))))
    re = [sum(switch[sl[i]])%2 for i in range(m)]
    if pl == re:
        cnt +=1

print(cnt)

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

all_bit = []
for i in range(2**N):
  bit_li = [0] * N
  for j in range(N):
    if (i >> j) & 1:
      bit_li[j] = 1
  all_bit.append(bit_li)

count = 0
for i in all_bit:
  light_li = [0] * M
  for j in range(len(switch_li)):
    for k in range(N):
      if i[k] == 1:
        if k+1 in switch_li[j][1:]:
          light_li[j] += 1
  m_count = 0        
  for a,b in zip(light_li, p_li):
    if a % 2 == b % 2:
      m_count += 1
    if m_count == M:
      count += 1
      
print(count)

Solution (Python):
def counter(n):
	temp = n
	c = 0
	while temp != 0:
		c += temp & 1
		temp = temp >> 1
	return c % 2

def main():
	n,m = map(int,input().split())
	light = []
	for i in range(m):
		line = list(map(int, input().split()))
		temp = 0
		for j in line[1:]:
			temp += 2 ** (j-1)
		light += [temp]
	lst = list(map(int,input().split()))
	ans = 0
	for i in range(2**(n)):
		flg = True
		for j in range(m):
			if lst[j] != counter(light[j] & i):
				flg = False
				break
		if flg:
			ans += 1
	print(ans)

main()

Solution (Python):
N, M = [int(s) for s in input().split()]
S = []
for _ in range(M):
    l = [int(s) for s in input().split()]
    S.append(l[1:])
P = [int(s) for s in input().split()]

result = 0
for i in range(2 ** N):
    if all(sum(["{:0{N}b}".format(i, N=N)[t - 1] == '1' for t in s]) % 2 == P[j] for j, s in enumerate(S)):
        result += 1

print(result)

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[s-1] for s in sw[i]])
    if (s-p[i])%2 != 0:
      bl = False
      break
  if bl:
    ans += 1
print(ans)

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

k = [0] * M
s = [0] * M


for m in range(M):
    line = list(map(int, input().split()))
    k[m] = line[0]
    
    s[m] = [line[l] - 1 for l in range(1, k[m] + 1)]

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

ans = 0
for i in range(2 ** N):
    tmp = [(i >> t) & 1 for t in range(N)]
    need = [sum([tmp[i] for i in l]) % 2 for l in s]
    if need == p:
        ans += 1
print(ans)

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

k = []
s = []
p = []

for i in range(m):
	int_arr = list(map(int , input().split()))
	k.append(int_arr[0])
	s.append(list(map(lambda x: x-1, int_arr[1:])))

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

on_pattern_cnt = 0

for s_pattern_int in range(2**n):
	s_pattern_binstr = str(bin(s_pattern_int)) 
	s_pattern_binstr = s_pattern_binstr[2:] 
	s_pattern_binstr = s_pattern_binstr.zfill(n)				
	s_pattern_binstr = s_pattern_binstr[::-1] 

	s_pattern = []
	for c in s_pattern_binstr:
		s_pattern.append(int(c))

	flag = True
	for i in range(m): 
		on_cnt = 0
		for j in range(k[i]): 
			if s_pattern[s[i][j]] == 1:
				on_cnt += 1

		if p[i] != on_cnt % 2:
			flag = False
			break

	if flag:
		on_pattern_cnt += 1


print(on_pattern_cnt)

Solution (Python):
import itertools
n,m=map(int,input().split())
ks=[[int(i) for i in input().split()]for i in range(m)]
p=[int(i) for i in input().split()]
swi=list(itertools.product([0,1], repeat=n))
cnt=0

for SWI in range(len(swi)):
    DK=[0 for i in range(m)]
    for onoff in range(len(swi[SWI])):
        if swi[SWI][onoff]==1:
            for i in range(m):
                for kkk in ks[i][1:]:
                    if kkk-1==onoff:
                        DK[i]+=1
                DK[i]%=2
    if DK==p:
        cnt+=1
print(cnt)

Solution (Python):
import numpy as np


N, M = map(int, input().split())
s_mat = np.zeros((M, N), dtype=int)
si_list = []
for i in range(M):
    si = list(map(int, input().split()))[1:]
    for s in si:
        s_mat[i, s-1] = 1
p_list = np.array(list(map(int, input().split())))


prob = 0
for i in range(2**N):
    i_list = []
    for k in range(N-1, -1, -1):
        if i >= 2**k:
            amari = 1
            i -= 2**k
        else:
            amari = 0
        i_list.append(amari)
        
    i_array = s_mat.dot(np.array(i_list)) % 2
    if np.all(i_array == p_list):
        prob += 1

print(prob)

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

pattern_count = 0
for n in range(2 ** N):
	for i, ks in enumerate(KS):
		switch_count = 0
		for s in ks[1:]:
			if n >> (s - 1) & 1:
				switch_count += 1
		else:
			if switch_count % 2 != P[i]:
				break
	else:
		pattern_count += 1
print(pattern_count)

Solution (Python):
import numpy as np
from itertools import product

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

for i in range(M):
    k, *s = map(int, input().split())
    s = [x - 1 for x in s]
    S[i, s] = 1
p = np.array(list(map(int, input().split())), dtype=np.int)

cnt = 0
for i in product([0, 1], repeat=N):
    a = np.array(i, dtype=np.int)  
    b = (np.dot(S, a) % 2).astype(np.int)
    if np.all(b == p):
        cnt += 1
print(cnt)

Solution (Python):
def count_bit(x):
    res = 0
    while x > 0:
        res += x % 2
        x //= 2
    return res


n, m = map(int, input().split())
k = [0] * m
for i in range(m):
    x = list(map(int, input().split()))
    k[i] = sum(map(lambda l: 2**(l-1), x[1:]))
p = list(map(int, input().split()))

res = 0
for b in range(2**n):
    for i in range(m):
        x = b & k[i]
        if count_bit(x) % 2 != p[i]:
            break
    else:
        res += 1
print(res)

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(1<<N): 
    count_2 = -1
    bit = list(str(bin(i))) 
    fail = 0
    
    
    ketaume = (1<<N) // 2 + 2 - len(bit) 
    if ketaume > 0:
        for i in range(ketaume):
            bit.insert(2, "0")
    
    for s in S: 
        count_2 += 1 
        count = 0
        for t in s: 
            
            if int(bit[-t]) == 1:
                count += 1 
                
        
                
        
        
        
        if not count % 2 == p[count_2]:
            fail = 1 
            break
    if fail == 0:
        
        ans += 1
        
print(ans)

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

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

ans = 0
for bits in range(2**n):
    flag = True
    for i in range(m):
        on_sum = 0
        for switch in s[i]:
            on_sum += ((bits >> (switch - 1)) & 1)
        flag = flag and ((on_sum % 2) == p[i])
    if flag:
        ans += 1

print(ans)

Solution (Python):
N,M=[int(i) for i in input().split()]
joints=[]
patterns=[]
for i in range(M):
	a=[int(j) for j in input().split()]
	joints.append(a[1:])
ans=input().split()
def f(x,i):
	if i==N:
		patterns.append(x)
		return
	f(x+"0",i+1)
	f(x+"1",i+1)
f("",0)
res=0
for pattern in patterns:
	for i in range(len(joints)):
		on=0
		for j in joints[i]:
			if pattern[j-1]=="1":
				on+=1
		if on%2==int(ans[i]):
			if i==len(joints)-1:
				res+=1
			else:
				continue
		else:
			break
	

print(res)

Solution (Python):
from sys import exit
from itertools import product

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

light = {}

for i in range(M):
    light[i] = list(map(int, input().split()))
    light[i].pop(0)

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

count = 0
for i in product([1, 0], repeat=N):
    clear = True
    for j in range(M):
        s = 0
        for k in light[j]:
            if i[k - 1] == 1:
                s += 1

        if s % 2 != p[j]:
            clear = False
            break
    if clear:
        count += 1

print(count)

Solution (Python):
N,M = map(int,input().split())
S = []
for i in range(M):
    S.append(list(map(int,input().split()))[1:])
P = list(map(int,input().split()))
res = 0
for i in range(2**N):
    ON = 0
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if (i >> s-1)&1 == 1:
                cnt += 1
        if cnt%2 == P[j]:
            ON += 1
    if ON == M:
        res += 1 
print(res)

Solution (Python):
n, m = map(int, input().split())
ks = [[0] for i in range(m)]
jud = []
for i in range(m):
    tmp = list([int(i)-1 for i in input().split()])
    ks[i] = tmp[1:]
jud = list(map(int, input().split()))

ans = 0
c = True
for i in range(2 ** n):
    c = True
    ib = format(i, 'b')
    for iks, j in enumerate(ks):
        ch = 0
        for m in j:
            if len(ib) >= m+1:
                ch += int(ib[-m-1])
        if ch % 2 != jud[iks]:
            c = False
            break
    if c:
        ans += 1
print(ans)

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

lamp=[]
switches=[]
temp=[]

for i in range(m):
    temp=list(map(int,input().split()))
    lamp.append(temp.pop(0))
    switches.append(temp)
    temp=[]

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

bit_list=[]

for i in range(2**(n)):
    bit_list.append(bin(i)[2:].zfill(n))

ans = 0

for b in bit_list:
    flag = 0
    for s,p in zip(switches,modul):
        sum = 0
        for k in range(len(s)):
            sum=sum+int(b[s[k]-1])
        if sum%2 != p:
            flag = 1
            break
    if flag == 0:
        ans=ans+1

print(ans)

Solution (Python):


"""
Created on Mon Jun 10 22:22:57 2019

@author: YudNK
"""

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

def binaly(n):
    d = n
    binaly = [0 for i in range(N)]
    m = 0
    while d >= 1:
        binaly[m] = d % 2
        d = d // 2
        m += 1
    return binaly

pattern = 0
for i in range(2**N):
    sample = binaly(i)
    count = 0
    for j in range(M):
        sum = 0
        for k in range(list[j][0]):
            sum += sample[list[j][k + 1] - 1]
        if sum%2 == p[j]:
            count += 1
    if count == M:
        pattern += 1
print(pattern)

Solution (Python):
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
s_list = [list(map(int, input().split())) for _ in range(m)]
p_list = list(map(int, input().split()))
patterns = []
for i in range(2**n):
    patterns.append(bin(i)[2:].zfill(n))
cnt = 0
for pattern in patterns:
    flag = 1
    for s, p in zip(s_list, p_list):
        if sum([int(pattern[i-1]) for i in s[1:]]) % 2 != p:
            flag = 0
            break
    if flag == 1:
        cnt += 1
print(cnt)

Solution (Python):
N,M=map(int,input().split())
S=[]
sw=[0]*N

for i in range(M):
    s=list(map(int,input().split()))[1:]
    S+=[s]

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


for k in range(2**N):
    flag=0
    b=bin(k)
    bi1=str(b[2:].zfill(N))
    bi=[int(_) for _ in bi1]
    for i in range(M):
        sm=0
        for j in range(len(S[i])):
            sm+=bi[S[i][j]-1]
        if sm%2!=p[i]:
            flag=1
            break
    if flag==0:
        count+=1


print(count)

Solution (Python):
def bitcount(bit):
    return bin(bit).count("1")

s = []
kmask = []
n,m = map(int,input().split())

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

for i in s:
    mask = 0
    for j in i[1:]:
        mask |= 1<<(j-1)        
    kmask.append(mask)

result = 0
for i in range(1<<n):
    ok = True
    for mask,odd in zip(kmask,p):
        bc = bitcount(i&mask)
        if((bc&1)!=odd):
            ok = False
            break
    if ok:
        result += 1

print(result)

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(1<<N): 
    
    for m in range(M):  
        count = 0
        for s in S[m]:
            if i & (1<<(s-1)) != 0:
                count += 1
                
        if count%2 != p[m]:
            break
    else:
        
        ans +=1
print(ans)

Solution (Python):



N, M = map(int, input().split())
tmp = []
k_i = []
p = []

for i in range(M):
    tmp = map(int, input().split())
    k_i.append(list(tmp))
p = list(map(int, input().split()))

det=[]
success = 0

for i in range(2**N):
    sw_status = format(i,'b').zfill(N)
    sw_status = list(map(int, sw_status))
    det=[]
    for k in range(M):
        det_j =0
        for j in range(k_i[k][0]):
            det_j += sw_status[k_i[k][j+1]-1]
        if p[k] == det_j % 2:
            det.append(1)
        else:
            det.append(0)
    if sum(det) == M:
        success += 1
print(success)

Solution (Python):
n, m = map(int, input().split())
lst = [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
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    all_lightup = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
          all_lightup = False
          break
    if all_lightup:
        ans += 1

print (ans)

Solution (Python):
n, m = map(int, input().split())
lst = [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
    for j in range(n):
        if i>>j & 1:
            for k in range(m):
                if j+1 in lst[k][1:]:
                    bulb[k] += 1

    flag = True
    for l in range(m):
        if bulb[l] % 2 != p[l]:
            flag = False
    if flag:
        ans += 1

print (ans)

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

sw2lmp = [[] for _ in range(N)]
for i in range(M):
    k, *s = map(int, input().split())
    s = tuple(map(lambda x: x - 1, s))
    for ss in s:
        sw2lmp[ss].append(i)
p = tuple(map(int, input().split()))

cnt = 0
for i in range(1 << N):
    state = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            for lmp in sw2lmp[j]:
                state[lmp] += 1
    if all(x % 2 == p[i] for i, x in enumerate(state)):
        cnt += 1
print(cnt)

Solution (Python):
import itertools

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 p in itertools.product([True, False], repeat=N):
    for i in range(M):
        ok = True if P[i] == 0 else False
        for s in S[i]:
            ok ^= p[s - 1]
        if not ok:
            break
    if ok:
        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()))

b=[]
for k in range(2**n):
  b.append(format(k,'0'+str(n)+'b'))

ans=0
for i in range(2**n):
  cton=0
  for j in range(m):
    ct=0
    for k in range(1,l[j][0]+1):
      if b[i][l[j][k]-1]=='1':ct+=1
    if ct%2==p[j]:cton+=1
  if cton==m:ans+=1
print(ans)

Solution (Python):
n,m = map(int,input().split())
s = []
k = []
p = []
count = 0
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    
    for j in range(k[i]):
        s[i][j] = int(q[j])
        
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
        


       
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%2)
        i = i // 2
    
    q = 0
    for j in range(m):
        wa = 0
        for l in range(k[j]):
            wa += list[s[j][l]-1]
        
        if wa%2 == p[j]:
            q += 1
            
        else:
            break
    if q == m:
        count += 1



    


print(count)

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

count = 0

for i in range(2**N): 
    c = [0] * M
    for j in range(N): 
        if (i >> j) & 1: 
            for k in range(M): 
                if j+1 in lst[k][1:]:
                    c[k] += 1
    flag = True
    for l in range(M):
        if c[l]%2 != p[l]:
            flag = False
    if flag:
        count += 1


print (count)

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

count = 0

for i in range(2**n):
    switches =str(format(i, 'b').zfill(n))
    lights = ""
    for light in range(m):
        s_on = 0
        for connect in s[light]:
            if switches[connect-1] == "1":
                s_on += 1
        if s_on % 2 == p[light]:
            lights += "1"
    if lights == "1" * m:
        count += 1
print(count)

Solution (Python):
import sys
import itertools

N, M = map(int, input().split())
S = [[int(x) for x in sys.stdin.readline().split()][1:] for _ in range(M)]
P = [int(x) for x in input().split()]

ans = 0

for state in itertools.product([0, 1], repeat=N):
    is_ans = True
    for bulb, p in zip(S, P):
        connected = 0
        for idx in bulb:
            if state[idx - 1] == 1:
                connected = connected + 1
        if connected % 2 != p:
            is_ans = False
            break
    if is_ans:
        ans = ans + 1

print(ans)

Solution (Python):
N,M = map(int,input().split())
S = []
for _ in range(M):
    S.append(list(map(int,input().split()))[1:])
P = list(map(int,input().split()))
res = 0
for i in range(2**N):
    tmp = 0
    for j in range(M):
        ON = 0
        for s in S[j]:
            if (i >> s-1)&1 == 1:
                ON += 1
        if ON % 2 == P[j]:
            tmp += 1
    if tmp == M:
        res += 1
print(res)

Solution (Python):
import copy

L=[]

def check(M,p,tmp):
  n_ok=0
  for i in range(len(L)):
    sum=0
    for l in L[i]:
      sum+= 1 if tmp[l-1]==1 else 0
    if sum%2==p[i]:
      n_ok+=1
      
  if n_ok==M:
    return 1
  else:
    return 0

def rc(N,M,p,i,tmp):
  if i==N-1:
    return check(M,p,tmp)
  else:
    t1=copy.copy(tmp)
    t2=copy.copy(tmp)
    t1.append(0)
    t2.append(1)
    return rc(N,M,p,i+1,t1)+rc(N,M,p,i+1,t2)

N, M = map(int, input().split())
for _ in range(M):
    tmp = list(map(int,input().split()))
    L.append(tmp[1:])
p=list(map(int,input().split()))
S=[0 for _ in range(N)]

print(rc(N,M,p,-1,[]))

Solution (Python):
from itertools import combinations

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

A = {i: [] for i in range(N)}

for i in range(M):
  line = [int(i) for i in input().strip().split(' ')]
  for s in line[1:]:
    A[s - 1].append(i)

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

cmb = []
for i in range(N + 1):
  cmb.extend(list(combinations(range(N), i)))

counter = 0
for c in cmb:
  
  tmp = [0] * M
  for i in c:
    for j in A[i]:
      tmp[j] = (tmp[j] + 1) % 2
  if tmp == P:
    counter += 1

print(counter)

Solution (Python):
import sys
N, M = map(int, input().split())
k_list_list = []
for m in range(M):
    k_list_list.append(list(map(int, input().split()[1:])))
p_list = list(map(int, input().split()))
    
def add_num(on_off_list_list):
    new_list = []
    for on_off_list in on_off_list_list:
        for i in [[0], [1]]:
            new_list.append(on_off_list+i)
    return new_list

def create_on_off_list(N):
    on_off_list_list = [[]]
    for n in range(N):
        on_off_list_list = add_num(on_off_list_list)
    return on_off_list_list

def check(k_list, p, on_off_list):
    total = 0
    for k in k_list:
        k -= 1
        swich = on_off_list[k]
        if swich == 1:
            total += 1
    if total%2 == p:
        return True
    else:
        return False

def main():
    on_off_list_list = create_on_off_list(N)
    ans = 0
    for on_off_list in on_off_list_list:
        for k_list, p in zip(k_list_list, p_list):
            if check(k_list, p, on_off_list): continue
            else: break
        else:
            ans += 1
    print(ans)
    
main()

Solution (Python):
from itertools import product


def bit(n,m):
    bi = list((product([i for i in range(n)],repeat = m)))
    return bi

if __name__ == "__main__":
    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
    petterns = bit(2,N)
    for pettern in petterns:
        for m in range(M):
            cnt = 0
            for s in S[m]:
                
                if pettern[s-1] == 1:
                    cnt += 1
            if cnt %2 != P[m]:
                break
        else:
            ans += 1
    print(ans)

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):
import collections
N,M=map(int,input().split())

ki=[]
k_sw=[] 
for i in range(M):
    terms = input().split()
    ki.append(int(terms[0]))
    k_sw.append([])
    for j in range(1,len(terms)):
        k_sw[i].append(int(terms[j]))
P=list(map(int,input().split()))

def is_all_on(swb):
    all_on = True
    for i in range(M):
        
        sws = k_sw[i]
        total = 0
        for s in sws:
            total += swb[s-1]
        if total % 2 != P[i]:
            all_on = False
            break
    return all_on

on_num = 0
for swp in range(0,2**N):
    binary_pattern = format(swp,'0'+str(N)+'b')
    blist = []
    for b in binary_pattern:
        blist.append(int(b))
    if is_all_on(blist):
        on_num += 1
print(on_num)

Solution (Python):
N,M = map(int,input().split())
L = []
for i in range(M):
  L.append(list(map(int,input().split())))
P = list(map(int,input().split()))
def Base_10_to_n(X,n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n),n)+str(X%n)
  return str(X%n)
n = 2
ans = 0
for X in range(n**N):
  STR = Base_10_to_n(X,n).zfill(N)
  flag = True
  for i in range(len(L)):
    t = 0
    for j in range(1,L[i][0]+1):
      t += int(STR[L[i][j]-1])
    if t%2 != P[i]:
      flag = False
      break
  if flag:
    ans += 1
print(ans)

Solution (Python):
from numpy import *

n, m = map(int, input().split())
s = [[int(x) for x in input().split()][1:] for y in range(m)]
p = [int(z) for z in input().split()]
ans = 0

for i in range(2**n):
    b = array([(i>>j)&1 for j in range(n)])
    if [sum(b[array(k) - 1]) % 2 for k in s] == p:
        ans += 1
print(ans)

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


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

ans = 0

for i in range(1 << N):  
    for mask in range(M):
        ans_2 = 0
        for s in SSS[mask]:
            if (1 << s-1) & i != 0:
                ans_2 += 1

        if ans_2 % 2 != P[mask]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from numpy import *
n,m = map(int, input().split())

s = [[int(j) for j in input().split()][1:] for i in range(m)]
p = [int(i) for i in input().split()]

ans = 0

for i in range(2**n):
    b = array([(i>>j)&1 for j in range(n)])
    if [sum(b[array(k)-1]) % 2 for k in s] == p:
        ans += 1
print(ans)

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

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

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

count=0
flag=True
for i in range(1<<n):
    flag=True
    for j in range(m):
        count2=0
        for l in k[j]:
            if i & (1<<(l-1)):
                count2+=1
        if not count2%2==p[j]:
            flag=False
    if flag:
        count+=1

print(count)

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(1<<N): 
    
    for m in range(M):  
        count = 0
        for s in S[m]:
            if i & (1<<(s-1)) != 0:
                count += 1
        if count%2 != p[m]:
            break
    else:
        ans +=1
print(ans)

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


switches = [[] for i in range(pow(2,n))]
for index in range(n):
    div =  pow(2,index)
    for i in range(pow(2,n)):
        term = i // div
        if term % 2 ==0:
            switches[i].append(0)
        else:
            switches[i].append(1)


light_switch = []
for _ in range(m):
    tmp = list(map(int, input().split()))
    tmp.pop(0)
    light_switch.append(tmp)


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

pattern_num = 0
for s in switches:
    all_on_flg = True
    
    for num, light in enumerate(light_switch):
        on_num = 0
        for ls in light:
            if s[ls-1] == 1:
                on_num += 1
        if on_num % 2 != p[num]:
            
            all_on_flg = False
            break
    if all_on_flg:
        pattern_num += 1
print(pattern_num)

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

from itertools import product

bit = product([1, 0], repeat=N)

total = 0
for switch in bit:
    for i, m in enumerate(mat):
        ison = 0
        for j in m:
            ison += switch[j] 
        match = ison % 2 == p[i]
        if not match:
            break
    else:
        total += 1
print(total)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
S = []
for i in range(M):
    s = list(map(int, input().split()))
    k = s.pop(0)
    assert len(s) == k
    S.append(s)
P = list(map(int, input().split()))
assert len(P) == M

def on(s, p, onoff):
    return sum(onoff[i - 1] for i in s) % 2 == p

n = 0
for onoff in product(range(2), repeat=N):
    if all(on(s, p, onoff) for s, p in zip(S, P)):
        n += 1

print(n)

Solution (Python):
import sys

s = []
num = 0
for line in sys.stdin:
    if int(num) == 0:
        N, M = map(int, line.strip().split(" "))
    elif int(num) < M + 1:
        i = num - 1
        s.append(line.strip().split(" ")[1:])
    else:
        p = line.strip().split(" ")
    num += 1



state_num = pow(2, N)
clear_num = 0

for i in range(state_num):
    states = format(i, 'b').zfill(N)
    

    all_on = True
    for j in range(M):
        sws = s[j]
        on_num = 0
        
        for sw in sws:
            
            if states[int(sw)-1] == "1":
                on_num += 1
        
        if on_num % 2 != int(p[j]):
            all_on = False
        

    if all_on:
        clear_num += 1

print(clear_num)