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):
    onoff = [0] * m
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in ks[k][1:]:
                    onoff[k] +=1
    cnt = 0
    for l in range(m):
        if onoff[l] % 2 == p[l]:
            cnt += 1
        if cnt == m:
            ans += 1
print(ans)

Solution (Python):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = [LIST() for i in range(m)]
p = LIST()
ans = 0

for i in range(2**n):
    sw = []
    for j in range(n):
        sw.append(( i >> j ) & 1)
    for j in range(m):
        reg = 0    
        for k in range(1, s[j][0]+1):
            reg += sw[s[j][k]-1]
        if reg % 2 != p[j]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
def INT():
    return int(input())

def MI():
    return map(int, input().split())

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

N, M = MI()
K, switch = [], []

for _ in range(M):
    k, *s = MI()
    K.append(k)
    switch.append(s)
    
p = LI()
ans = 0

for i in range(1 << N):
    on = [False] * N
    
    for j in range(N):
        if (i >> j) & 1:
            on[j] = True
    
    can = True
    
    for k in range(M):
        tmp = 0
        for s in switch[k]:
            tmp += on[s - 1]
            
        if tmp % 2 != p[k]:
            can = False
            break
    
    ans += can
    
print(ans)

Solution (Python):










import sys

def input(): return sys.stdin.readline().rstrip()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]

def OutH(lst, deli=' '): print(deli.join(map(str, lst)))
def OutV(lst): print('\n'.join(map(str, lst)))

sys.setrecursionlimit(10 ** 6)

int1 = lambda x: int(x) - 1

INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)


N, M = iInM()
KS = iInLD(M)
P = iInLH()

ans = 0
for i in range(2**N):
    isOn = [False] * N
    for j in range(N):
        isOn[N-1-j] = ((i >> j) & 1) == 1
    for j in range(M):
        cnt = 0
        for k in range(KS[j][0]):
            cnt += isOn[KS[j][k+1]-1]
        if cnt % 2 != P[j]:
            break
    else:
        ans += 1
    

print(ans)

Solution (Python):

import itertools
N, M = map(int,input().split())
s = [list(map(int, input().split())) for _ in range(M)]
p = list(map(int, input().split()))
ans = 0
   
for i in itertools.product([0,1], repeat=N):
    dame = 0
    for j in range(M):
        temp = p[j]
        for k in s[j][1::]:
            temp += i[k-1]
        if temp%2:
            dame = 1
    if not dame:
        ans += 1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    N, M = map(int, input().split())
    
    
    S = list(list(map(int, input().split()))[1:] for i in range(M)) 
    ps = tuple(map(int, input().split()))
    
    ans=0
    for i in range(2**N):
        cnt=0
        for j in range(M):
            p=ps[j]
            tot=0
            for s in S[j]:
                tot^=((i>>(s-1))&1)
            if tot==p:
                cnt+=1
        if cnt==M:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

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


def main():
    n, m = map(int, input().split())
    s = np.full((m, n), False, dtype=bool)

    for i in range(m):
        line = list(map(int, input().split()))
        for e in line[1:]:
            s[i][e-1] = True

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

    ans = 0

    for pat in product((False, True), repeat=n):
        for i in range(m):
            if np.sum(np.logical_and(s[i], pat)) % 2 != p[i]:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

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

a = 0
for bit in range(1 << N):
    flag = True
    for i in range(M):
        c = 0
        for j in K[i][1:]:
            if bit & (1 << (j - 1)):
                c += 1
        if c % 2 != P[i]:
            flag = False
            break
    if flag:
        a += 1

print(a)

Solution (Python):

n, m = map(int, input().split())
e = [[*map(int, input().split())][1:] for _ in range(m)]
p = [*map(int, input().split())]

c = 0

for i in range(2**n):
    count = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if j + 1 in e[k]:
                    count[k] = (count[k] + 1) % 2
    if count == p:
        c += 1
print(c)

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 b in range(2 ** n):
  onswitch = [i + 1 for i in range(n) if (b >> i) & 1]
  if all(sum(o in s for o in onswitch) % 2 == p for s, p in zip(S, P)):
    ans += 1
    
print(ans)

Solution (Python):

N,M = map(int,input().split())
K = []
for i in range(M):
  lst = list(map(int,input().split()))
  K.append([i-1 for i in lst[1:] ])

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

for i in range(1<<N):
  on = []
  for j in range(N):
    if (i>>j)&1:
      on.append(j)

  flg = True
  for m in range(M):
    k = K[m]
    tmp = 0
    for s in k:
      if s in on:
        tmp += 1
    p = P[m]
    if tmp % 2 != p:
      flg = False
      break

  if flg:
    res += 1

print(res)

Solution (Python):
from itertools import product
n, m = map(int, input().split())
switches = []
for _ in range(m):
    k, *s = map(lambda x: int(x)-1, input().split())
    switches.append(s)
p = list(map(int, input().split()))

ans = 0
for subset in product((0, 1), repeat=n):
    for j in range(m):
        on_cnt = sum(subset[s] for s in switches[j])
        if on_cnt % 2 != p[j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import itertools
 
N, M = map(int, input().split())
lights = []
for m in range(M):
    tmp = list(map(int, input().split()))
    lights.append(tmp[1:])
    
    
 
 
P = list(map(int, input().split()))
 
ans = 0
for product in list(itertools.product([0, 1], repeat=N)):
    for light in range(len(lights)):
        cnt = 0
        for l in lights[light]:
            cnt += product[l-1]
        if cnt % 2 != P[light]:
            break
        if light == len(lights) - 1:
            ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
answer = 0
li = []
for i in range(m):
    li.append(list(map(int,input().split())))
li1 = list(map(int,input().split()))
for i in range(2**n):
    b = "0"*(n-len(bin(i))+2)+bin(i)[2:]
    libi = [int(b[s]) for s in range(n)]
    c = 0
    for j in range(m):
        c1 = 0
        for k in range(li[j][0]):
            if libi[li[j][k+1]-1] == 1:
                c1 += 1
        if c1 % 2 == li1[j]:
            c += 1
    if c == m:
        answer += 1
print(answer)

Solution (Python):
import itertools

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


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

ans = 0
for product in list(itertools.product([0, 1], repeat=N)):
    for light in range(len(lights)):
        cnt = 0
        for l in lights[light]:
            cnt += product[l-1]
        if cnt % 2 != P[light]:
            break
        if light == len(lights) - 1:
            ans += 1
print(ans)

Solution (Python):


n, m = map(int, input().split())
ks_l = [[int(x) for x in input().split()] for y in range(m)]
p_l = [int(x) for x in input().split()]

ans = 0

for i in range(2**n):
    for j in range(m):
        _tmp = 0
        for k in range(ks_l[j][0]):
            if((i >> (ks_l[j][k+1] - 1)) & 1):
                _tmp += 1
        if (_tmp % 2) != p_l[j]:
            break
    else:
        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_or_off = [0]*M
  for j in range(N):
    if (i>>j)&1:
      for k in range(M):
        if j+1 in ks[k][1:]:
          on_or_off[k] += 1
  cnt = 0
  for l in range(M):
    if on_or_off[l]%2 == P[l]:
      cnt += 1
  if cnt == M:
    ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
K = []
S = []
for _ in range(m):
    k, *s = map(int, input().split())
    K.append(k)
    S.append(s)
P = list(map(int, input().split()))

def ok_by_switch_state(ONs):
    for i in range(m):
        on_cnt = 0
        for s in S[i]:
            s -= 1
            on_cnt += (ONs & 1<<s) != 0
        if on_cnt % 2 != P[i]:
            return False
    else:
        return True
ans = 0
for i in range(2 ** n):
    ans += ok_by_switch_state(i)
print(ans)

Solution (Python):

from itertools import product
N, M = map(int, input().split())
S = [list(map(int, input().split()))[1:] for _ in range(M)]

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

ret = 0
for p in product([0,1], repeat=N):
    f = True
    for i in range(M):
        c = 0
        for s in S[i]:
            c += p[s-1]
        if c%2 != P[i]:
            f = False
    if f: ret += 1

print(ret)

Solution (Python):
n,m = map(int,input().split())
klist = []
swlist = []
ans = 0
for s in range(m):
	k,*sw = list(map(int,input().split()))
	klist.append(k) 
	swlist.append(sw) 
pwlist = list(map(int,input().split())) 

for i in range(2**n):
	check = True
	for lump in range(m):
		cnt = 0
		for j in range(klist[lump]):
			if (i>>swlist[lump][j]-1)&1==1:
				cnt += 1
		if cnt%2 != pwlist[lump]:
			check = False
	if check == True:
		ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
klist = []
swlist = []
ans = 0
for s in range(m):
	k,*sw = list(map(int,input().split()))
	klist.append(k) 
	swlist.append(sw) 
pwlist = list(map(int,input().split())) 

for i in range(2**n):
	check = True
	for lump in range(m):
		cnt = 0
		for j in range(klist[lump]):
			if (i>>swlist[lump][j]-1)&1==1:
				cnt += 1
		if cnt%2 != pwlist[lump]:
			check = False
	if check == True:
		ans += 1
print(ans)

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

Solution (Python):
import itertools
N,M = list(map(int,input().split()))
k_lis = []
for i in range(M):
    k_lis.append(list(map(int,input().split())))
P = list(map(int,input().split()))
switch_list = list(itertools.product('01',repeat = N))
ans = 0
sub = 0

for sl in range(len(switch_list)):
    
    if True:
        flag = 0
        for i in range(M):
            counter = 0
            for j in range(1,k_lis[i][0]+1):
                if switch_list[sl][k_lis[i][j]-1] == '1' :
                    counter += 1
                    
            if counter %2 != P[i]:
                flag = 1
                break
        if flag == 0:    
            ans += 1
print(ans)

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

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for k, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[k]:
      break
  else:
    output += 1
print(output)

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

for i in range(2 ** n):
  lights = []
  for j in range(n+1):
    if ((i >> j) & 1):
      lights.append(j+1)
      
  for inde, l in enumerate(l_list):
    if len(set(l[1:]) & set(lights)) % 2 != p[inde]:
      break
  else:
    output += 1
print(output)

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

bag = []
for n in range(2**N):
    bag_ = []
    for n_ in range(N):
        bag_.append((n >> n_)&1)
    bag.append(bag_)

def get_ON_list(b):
    ON_list=[]
    for m in range(M):
        S_on=0
        for s in S[m]:
            S_on += b[s-1]

        ON_list.append(S_on%2)
    return ON_list

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

ans=0
for b in bag:
    ON_list=get_ON_list(b)
    ans_=1
    for on_idx,on in enumerate(ON_list):
        p=P[on_idx]
        if on != p:
            ans_=0
            break
    ans += ans_
print(ans)

Solution (Python):
n,m=map(int,input().split())
switch_list=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    result=[0]*m
    for j in range(n):
        if (i>>j)&1:
            for k in range(m):
              if j+1 in switch_list[k][1:]:
                  result[k]+=1
    for l in range(m):
        if (result[l]%2)!=p[l]:
            break
    else:
        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 bit in range(1<<N):
    count = [0]*M
    for i in range(N):
        if (bit >> i) & 1:
            for a in range(M):
                if i+1 in ks[a][1:]:
                    count[a] +=1
    a = 0
    for i in range(M):
        if count[i] % 2 == p[i]:
            a += 1
            if a == M:
                ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
list1=[]
for i in range (M):
    a=list(map(int,input().split()))
    list1.append(a)
P=list(map(int,input().split()))
switch=[0]*N
count=0
for i in range (2**N):
    switch=[0]*N
    ans=0
    for j in range (N):
        if ((i>>j)&1):
            switch[N-1-j]=1
    for l in range(1,M+1):
        con=0
        for k in range(1,len(list1[l-1])):
            con+=switch[list1[l-1][k]-1]
        if con%2!=P[l-1]:
            ans=1
    if ans==0:
        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()))) 
    s[i].pop(0) 
p = list(map(int,input().split()))

res = 0

for bit in range(1<<N): 
    ok = True
    for i in range(M):
        con = 0
        for v in s[i]: 
            if bit & (1<<(v-1)): con += 1 
        if con % 2 != p[i]: ok = False 
    if ok: res += 1 
print(res)

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

res = 0

for bit in range(1<<N):
    ok = True
    for i in range(M):
        con = 0
        for v in s[i]:
            if bit & (1<<(v-1)): con += 1
        if con % 2 != p[i]: ok = False
    if ok: res += 1
print(res)

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

switchMap = []
for i in range(N):
    switchMap.append([])
for i, s in enumerate(S):
    for ss in s:
        switchMap[ss-1].append(i)

count = 0
for i in range(pow(2, N)):
    switches = bin(i).replace("0b", "").zfill(N)
    light = [0] * M
    for j, switch in enumerate(switches):
        if switch == '1':
            for s in switchMap[j]:
                light[s] += 1

    flag = True
    for j, l in enumerate(light):
        if l % 2 != P[j]:
            flag = False
            break

    if flag:
        
        count += 1

print(count)

Solution (Python):
def main():
    N, M = map(int, input().split())
    lights = []
    for i in range(M):
        lights.append(set(list(map(int, input().split()))[1:]))
    P = list(map(int, input().split()))
    switch_combs = []

    for i in range(2**N):
        tmp_comb = set()
        for j in range(N):
            if (i >> j) & 1:
                tmp_comb.add(j+1)
        switch_combs.append(tmp_comb)
    num_sum = 0

    for comb in switch_combs:
        for i in range(len(lights)):
            num_match = len(lights[i] & comb)
            if not num_match % 2 == P[i]:
                break
        else:
            num_sum += 1
    print(num_sum)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import product

n,m = map(int, input().split())
ks = []
for _ in range(m):
    sl = list(map(int, input().split()))
    ks.append(sl[1:])

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


ans = 0
pattern = 2
ite = product(range(pattern),repeat=n)
for it in ite:
    s_on_off = list(it)
    for bulb, p in zip(ks, pl):
        curr_cnt = 0
        for s in bulb:
            if s_on_off[s-1] == 1: curr_cnt+=1
        if curr_cnt%2 != p:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from collections import defaultdict

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

for i in range(1, m + 1):
    _, *x = map(int, input().split())
    for j in x:
        s[j].append(i)

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


ans = []
for i in range(2**n):
    tmp = [0] * len(p)
    for j in range(n):
        if ((i >> j) & 1):
            for k in s[j + 1]:
                tmp[k - 1] += 1
    if all([x % 2 == y for x, y in zip(tmp, p)]):
        ans.append(True)
    else:
        ans.append(False)

print(sum(ans))

Solution (Python):
from itertools import product

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

count = 0
for S in product((0, 1), repeat=n):
  if all(sum(S[s - 1] for s in ks[1:]) % 2 == p for p, ks in zip(P, KS)):
    count += 1
print(count)

Solution (Python):


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k_m, s_m = l[0], l[1:]
        k.append(k_m)
        s.append(s_m)
    p = list(map(int, input().split()))

    return N, M, k, s, p


def lights_on(M: int, s: list, p: list, switches: int) -> bool:
    """
    電球がすべて点灯しているかどうかを確認する.

    Args:\n
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
        switches (int): スイッチの状態

    Returns:\n
        bool: 電球がすべて点灯していれば真、そうでなければ偽
    """
    result = True
    for m in range(M):
        switch_on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                switch_on_count += 1
        if switch_on_count % 2 != p[m]:
            result = False

    return result


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
    """
    
    ans = 0
    for switches in range(1 << N):
        if lights_on(M, s, p, switches):
            ans += 1

    
    print(ans)


if __name__ == "__main__":
    
    N, M, k, s, p = get_input()

    
    main(N, M, s, p)

Solution (Python):

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    
    N, M = list(map(int, input().split()))
    k, s = [], []
    for m in range(M):
        l = list(map(int, input().split()))
        k_m, s_m = l[0], l[1:]
        k.append(k_m)
        s.append(s_m)
    p = list(map(int, input().split()))

    return N, M, k, s, p


def lights_on(M: int, s: list, p: list, switches: int) -> bool:
    """
    電球がすべて点灯しているかどうかを確認する.

    Args:\n
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
        switches (int): スイッチの状態

    Returns:\n
        bool: 電球がすべて点灯していれば真、そうでなければ偽
    """
    result = True
    for m in range(M):
        switch_on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                switch_on_count += 1
        if switch_on_count % 2 != p[m]:
            result = False

    return result


def main(N: int, M: int, s: list, p: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): スイッチの数
        M (int): 電球の数
        s (list): 電球に対応するスイッチ
        p (list): スイッチと電球の点灯の関係
    """
    
    ans = 0
    for switches in range(1 << N):
        if lights_on(M, s, p, switches):
            ans += 1

    
    print(ans)


if __name__ == "__main__":
    
    N, M, k, s, p = get_input()

    
    main(N, M, s, p)

Solution (Python):


N, M = list(map(int, input().split()))
k, s = [], []
for m in range(M):
    l = list(map(int, input().split()))
    k_m, s_m = l[0], l[1:]
    k.append(k_m)
    s.append(s_m)
p = list(map(int, input().split()))


def lights_on(switches: int) -> bool:
    result = True
    for m in range(M):
        on_count = 0
        for s_m_km in s[m]:
            if switches & (1 << (s_m_km - 1)):
                on_count += 1
        if on_count % 2 != p[m]:
            result = False

    return result



ans = 0
for switches in range(1 << N):
    if lights_on(switches):
        ans += 1


print(ans)

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

wiring = []
for i in range(m):
    k, *s = map(int, input().split())
    
    for j in range(k):
        s[j] -= 1
    
    wiring.append(s)

p_i = [int(x) for x in input().split()]

ans = 0
for i in range(2**n):
    swiches = [-1] * n
    lamps = [0] * m
    for j in range(n):
        swiches[j] = (i >> j) & 1
        
    for j in range(m):
        cnt = 0
        for w in wiring[j]:
            if swiches[w] == 1:
                cnt += 1
        
        if cnt % 2 == p_i[j]:
            lamps[j] = 1
    
    if sum(lamps) == m:
        ans += 1
    
print(ans)

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()))
cnt = 0

for i in range(2**n):
    flg = True
    for j in range(m):
        s = 0
        for k in range(1,len(ks[j])):
            if i & (1 << ks[j][k]-1):
                s += 1
        if s % 2 != p[j]:
            flg = False
            break
    if flg:
        cnt += 1
print(cnt)

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

sm=0
for x in range(2**n):
    onlst=[0 for _ in range(m)]
    for i in range(n):
        if x>>i&1:
            for j in range(m):
                if i+1 in swi[j] :
                    onlst[j]+=1
    if [x%2 for x in onlst]==res : sm+=1
print(sm)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
l = [[int(i) for i in input().split()] for _ in range(m)]
p = [int(i) for i in input().split()]
c = 0
for sw in product((0, 1), repeat=n):
    for i in range(m):
        if sum(sw[si - 1] for si in l[i][1:]) % 2 != p[i]:
            break
    else:
        c += 1
print(c)

Solution (Python):
n, m = [int(i) for i in input().split()]
ks = [[int(i) for i in input().split()] for _ in range(m)]
p = [int(i) for i in input().split()]
cnt = 0
for i in range(2**n):
  on = set(j + 1 for j in range(n) if i >> j & 1 == 1)
  flag = True
  for j in range(m):
    _, *s = ks[j]
    flag &= len(on & set(s)) % 2 == p[j]
  cnt += flag
print(cnt)

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:
                cnt += 1
        if cnt % 2 != p[i]:
            judge = False
    if judge:
        res += 1
print(res)

Solution (Python):
import itertools
n,m=map(int,input().split())
lamp=[]
for _ in range(m):
    lamp_i=list(map(int,input().split()))
    lamp.append(lamp_i[1:])
p=list(map(int,input().split()))
ans=0
for bit in itertools.product([0,1],repeat=n):
    f=True
    for i in range(m):
        s_i=sum(bit[s-1] for s in lamp[i])
        if (s_i-p[i])%2!=0:
            f=False
            break
    if f:
        ans+=1
print(ans)

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()))
a=0
for bit in range(1<<n):
 for j in range(m):
  c=0
  for k in s[j][1:]:
   if bit&(1<<(k-1)):c+=1
  if c%2!=p[j]:break
 else:a+=1
print(a)

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

ans = 0

for i in range(2**n):
    flag = True
    for j in range(m):
        c = 0
        for v in s[j]:
            if i >> (v-1) & 1:
                c += 1
        if c%2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
f=lambda:[*map(int,input().split())]
n,m=f()
S=[f()[1:] for _ in [0]*m]
p=f()
print(sum(all(sum(i>>~-k for k in S[j])%2==p[j] for j in range(m)) for i in range(2**n)))

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
S=[[0]*n for _ in [0]*m]
for i in range(m):
  _,*s=f()
  for j in s: S[i][j-1]=1
p=[*f()]
print(sum(all(sum(i>>j&1*S[k][j] for j in range(n))%2==p[k] for k in range(m)) for i in range(2**n)))

Solution (Python):
f=lambda:map(int,input().split())
n,m=f()
S=[[0]*n for _ in range(m)]
for i in range(m):
  _,*s=f()
  for j in s: S[i][j-1]=1
p=[*f()]
a=0
for i in range(2**n):
  if all(sum(S[k][j] for j in range(n) if i>>j&1)%2==p[k] for k in range(m)): a+=1
print(a)

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

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


n = N
Switch = [[] for _ in range(n+1)]
ans = 0
for bit in range(2**n):
    cost = 0
    for i in range(n):
        mask = 1 << i
        if bit & mask:
            Switch[i+1] = 1
        else:
            Switch[i+1] = 0


    
    Light = [0 for _ in range(M)]
    for i in range(M):
        count = 0
        for s in S[i]:
            count += Switch[s]

        if count%2 == P[i]:
            Light[i] = 1

    if all(Light):
        ans += 1
print(ans)

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

ans = 0
for i in range(2 ** n):
    state = [0] * n
    flag = True
    for j in range(n):
        if (i >> j) & 1:
            state[j] = 1
    for k in range(m):
        c = 0
        for l in li[k]:
            c += state[l-1]
        if c%2 != p[k]:
            flag = False
            break
    if flag == True:
        ans += 1

print(ans)

Solution (Python):
n,m=map(int,input().split())
lst=[]
for i in range(m):
    a=[int(x) for x in input().split()]
    a=[x-1 for x in a]
    lst.append(a[1:])
p=[int(x) for x in input().split()]
ans=0

for i in range(2**n):
    on=[]
    light_on=0
    for j in range(n):
        if ((i>>j)&1):
            on.append(j)
    for j in range(m):
        num_on=0
        for k in range(len(lst[j])):
            if lst[j][k] in on:
                num_on+=1
        if (num_on%2)==p[j]:
            light_on+=1
    if light_on==m:
        ans+=1

print(ans)