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

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

for i in range(M):
    s = list(map(int, input().split()))[1:]
    for s_ in s:
        S[s_-1] ^= 1 << i
P_ = list(map(int, input().split()))
P = 0
for i, p in enumerate(P_):
    P ^= p << i


ans = 0
for i in range(1<<N):
    a = P
    for j, s in enumerate(S):
        if i>>j & 1:
            a^=s
    if a==0:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
d=[[0 for i in range(n)]for i in range(m)]
for i in range(m):
    x=list(map(int,input().split()))
    for j in range(1,x[0]+1):
        d[i][x[j]-1]=1
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    for j in range(m):
        tmp=0
        for k in range(n):
            if (1<<k)&i:
                tmp+=d[j][k]
        if tmp%2!=p[j]:
            break
    else:
        ans+=1
print(ans)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
S = []
for _ in range(M):
    _, *s = map(int, input().split())
    S.append(s)
P = [int(s) for s in input().split()]

cnt = 0
for ss in product([0, 1], repeat=N):
    for i in range(M):
        if sum(ss[sj - 1] for sj in S[i]) % 2 != P[i]:
            break
    else:
        cnt += 1

print(cnt)

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

KS = [list(map(int, input().split())) for _ in range(M)]
S = [[KS[m][i]-1  for i in range(1, len(KS[m]))] for m in range(M)]
p = list(map(int, input().split()))

def check(l):
    for m in range(M): 
        tmp_sum = 0
        for switch in S[m]:
            if l[switch]:
                tmp_sum +=1
        if tmp_sum%2 != p[m]:
            return False
    return True



ans = 0
for l in itertools.product([0,1],repeat=N):
    if check(l):
        ans += 1

print(ans)

Solution (Python):
import itertools

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

for i in range(m):
    a = input().split()
    for x in a[1:]:
        stl[int(x)-1].append(i)

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

count = 0
for comb in itertools.product([True, False], repeat=n):
    cs = [0 for _ in range(m)]
    for i, t in enumerate(comb):
        if t:
            for l in stl[i]:
                cs[l] += 1

    if all([cs[i] % 2 == ps[i] % 2 for i in range(m)]):
        count += 1

print(count)

Solution (Python):







import math, itertools, operator
from math import *
from math import factorial as fact
from operator import itemgetter, attrgetter
from itertools import permutations, combinations
from functools import reduce


from fractions import gcd

inf = float('inf')

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

def perm(a, b):
    import scipy.special
    return scipy.special.perm(a, b, exact = True)

def comb(a, b):
    import scipy.special
    return scipy.special.comb(a, b, exact = True)

def dfact(n):
    import scipy.special
    return scipy.special.factorial2(n, exact = True)

def prod(l):
    return reduce(operator.mul, l)

def input_ints(inp = input, sep = ' ', conv = int):
    return list(map(conv, inp().split(sep = sep)))



N, M = input_ints()
Smask = []
for i in range(M):
    l = input_ints()
    m = 0
    for j in l[1:]:
        m |= (1 << (j - 1))
    Smask.append(m)
P = input_ints()

def popcount(x):
    return bin(x).count('1')

cnt = 0
for i in range(1 << N):
    flag = True
    for j in range(M):
        mask = Smask[j]
        if popcount(i & mask) % 2 != P[j]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

Solution (Python):
def inpl(): return list(map(int, input().split()))

N, M = inpl()
T = [[] for _ in range(N)]
for i in range(M):
    _, *S = inpl()
    for s in S:
        T[s-1].append(i)
P = inpl()

ans = 0
for x in range(2**N):
    Q = [0]*M
    for i in range(N):
        if (x >> i) & 1:
            for t in T[i]:
                Q[t] += 1
    ans += P == [q%2 for q in Q]
print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, KS, P):

    ans = 0
    for s in product((0, 1), repeat=N):
        for j, ks in enumerate(KS):
            k = ks[0]
            c = 0
            for i in range(1, k+1):
                c += s[ks[i]-1]
            if c % 2 != P[j]:
                break
        else:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    KS = [read_int_n() for _ in range(M)]
    P = read_int_n()
    print(slv(N, M, KS, P))


if __name__ == '__main__':
    main()

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

answer = 0
from itertools import product
for sw in product([0,1], repeat=N):
  for p, ks in zip(P,KS):
    K = ks[0]
    S = ks[1:]
    if sum([sw[s-1] for s in S])%2 != p%2:  
      break
  else:
    answer += 1
    
print(answer)

Solution (Python):



import itertools


def solve(n, m, sss, ps):
    res = 0
    for switches in itertools.product((True, False), repeat=n):
        num_on = 0
        for i in range(m):
            if sum(switches[s] for s in sss[i]) % 2 == ps[i]:
                num_on += 1
            else:
                break
        if num_on == m:
            res += 1
    return res


def main():
    n, m = (int(z) for z in input().split())
    sss = [tuple(int(x) - 1 for x in input().split())[1:] for _ in range(m)]
    ps = [int(p) for p in input().split()]
    res = solve(n, m, sss, ps)
    print(res)


if __name__ == "__main__":
    main()

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 switch in range(2 ** N):
    for i, ksi in enumerate(ks):
        ki = ksi[0]
        si = ksi[1:]
        
        cnt = 0
        for j, sij in enumerate(si):
            cnt += (switch >> (sij - 1)) & 1
        
        if cnt % 2 != p[i]:
            break
        else:
            continue
    else:
        ans += 1

print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,M = inpl()
kk = []
ss = []
for i in range(M):
    ks = inpl()
    kk.append(ks[0])
    ss.append(ks[1:])

pp = inpl()

ans = 0
for bit in range(1<<N):
    on = [False]*N
    for b in range(N):
        if bit & (1<<b):
            on[b] = True
    for m in range(M): 
        k = kk[m]
        tmp = 0
        for n in range(N): 
            if on[n] and (n+1 in ss[m]):
                tmp += 1
        if tmp%2 != pp[m]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools

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

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

def check(status, switches, p):
    cnt = 0
    for s in status:
        if s in switches:
            cnt += 1
    return cnt % 2 == p

total = 0
for status in range(2**n):
    on = []
    for i in range(n):
        if status & 2**i:
            on.append(i+1)
    all_light = True
    for i in range(m):
        if not check(on, lights[i], ps[i]):
            all_light = False
            break
    if all_light:
        total += 1
print(total)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
sss = []
for _ in range(M):
    k, *ss = map(int, input().split())
    sss.append(ss)
ps = list(map(int, input().split()))

ans = 0
for ptn in product(range(2), repeat=N):
    numL = 0
    for ss, p in zip(sss, ps):
        numON = 0
        for s in ss:
            numON += ptn[s-1]
        if numON%2 == p:
            numL += 1
    if numL == M:
        ans += 1

print(ans)

Solution (Python):
def main():
    inp = readnumbers()
    ii = 0

    n = inp[ii]
    ii += 1
    m = inp[ii]
    ii += 1

    S = []
    for _ in range(m):
        k = inp[ii]
        ii += 1
        S.append([x-1 for x in inp[ii:ii+k]])
        ii += k
    P = inp[ii:ii+m]

    ans = 0
    for i in range(2**n):
        switch = [int(x) for x in bin(2**(n)+i)[3:]]
        for i in range(m):
            ssum = sum(switch[j] for j in S[i])
            if ssum%2 != P[i]:
                break
        else:
            ans += 1
    print ans











py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')


import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'


def readnumbers(zero = 0):
    conv = ord if py2 else lambda x:x
    A = []; numb = zero; sign = 1; i = 0; s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0' [0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-' [0]: sign = -1
            elif s[i] != b'\r' [0]:
                A.append(sign*numb)
                numb = zero; sign = 1
            i += 1
    except:pass
    if s and s[-1] >= b'0' [0]:
        A.append(sign*numb)
    return A

if __name__== "__main__":
  main()

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

tar = []
def brute_force(s, remain):
    if remain == 0:
        tar.append(s)
    else:
        brute_force(s + "0", remain - 1)
        brute_force(s + "1", remain - 1)


brute_force("", N)

ans = 0
for T in tar:
    flag = True
    for i in range(M):
        p = p_list[i]
        k = items[i][0]
        s_list = items[i][1:]
        tmp = 0
        for s in s_list:
            t = T[s-1]
            if t == "1":
                tmp += 1
        if tmp % 2 == p:
            continue
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10 ** 6 + 10)
from collections import defaultdict




def main():
    num_switch, num_ligh = map(int, input().split())

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

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

    ans = 0

    for i in range(2 ** num_switch):
        data = list(map(int, list(bin(i)[2:])))
        data = [0 for i in range(num_switch - len(data))] + data

        flg = 1

        for j in range(num_ligh):
            kari = 0
            
            for ele in ligh_data[j]:

                kari += data[ele - 1]
            if kari % 2 != flg_data[j]:
                flg = 0
                break

        if flg:
            ans += 1

    print(ans)




if __name__ == '__main__':
    main()

Solution (Python):
n, m = map(int, input().split())
mask = [0] * m
for i in range(m):
	l = list(map(int, input().split()))
	for x in l[1:]:
		mask[i] += 2 ** (x - 1)
p = list(map(int, input().split()))
ans = 0
cnt = [0] * (2 ** n)
for sta in range(2 ** n):
	now = sta
	while now > 0:
		cnt[sta] += now & 1
		now //= 2
	valid = True
	for i in range(m):
		if cnt[mask[i] & sta] & 1 != p[i]:
			valid = False
			break
	if valid:
		ans += 1
print(ans)

Solution (Python):
N,M=map(int,input().split())
table=[set() for i in range(N)]
for i in range(M):
    A=[int(i) for i in input().split()]
    B=A[1:]
    for b in B:
        table[b-1].add(i)
P=[int(i) for i in input().split()]

ans=0
for k in range(1<<N):
    U=[0]*M
    for j in range(N):
        if k&(1<<j):
            for x in table[j]:
                U[x]+=1
                U[x]%=2
    if U==P:
        ans+=1
        
print(ans)

Solution (Python):
from itertools import product

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

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

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

ans = sum(
    all(
        sum(
            t[j - 1]
            for j in s[i]
        ) % 2 == p[i]
        for i in range(M)
    )
    for t in product(range(2), repeat=N)
)

print(ans)

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

bulbs = []
for i in xrange(m):
    line = map(int, raw_input().strip().split())
    bulbs.append(line[1:])

p = map(int, raw_input().strip().split())

ans = 0
for i in xrange(1 << n):
    lit = 0
    for j in xrange(m):
        l = bulbs[j]
        on = 0
        for switch in l:
            switch -= 1
            if (i & (1 << switch)): on += 1
        if (on - p[j]) % 2 == 0:
            lit += 1
    if lit == m:
        ans += 1

print ans

Solution (Python):
N,M=map(int,input().split())
data=[]
for i in range(M):
    line=list(map(int,input().split()))
    data.append(line[1:])
P=list(map(int,input().split()))
def check(S):
    for x in range(M):
        cnt=0
        for s in data[x]:
            if S[s-1]=="1":
                cnt+=1
        if cnt%2!=P[x]:
            return False
    return True
ans=0
for i in range(pow(2,N)):
    S=bin(i)[2:]
    S="0"*(N-len(S))+S
    if check(S):
        ans+=1
print(ans)

Solution (Python):

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    M = int(buflist[1])
    K = []
    S = []
    for i in range(M):
        buf = input()
        buflist = buf.split()
        K.append(int(buflist[0]))
        S.append(list(map(int, buflist[1:])))
    buf = input()
    buflist = buf.split()
    P = list(map(int, buflist))
    on_pattern = 0
    for i in range(2 ** N):
        sw = []
        for j in range(N):
            sw.append(i >> j & 1 > 0)
        all_on = True
        for j in range(M):
            on_count = 0
            for x in S[j]:
                if sw[x-1]:
                    on_count += 1
            if on_count % 2 != P[j]:
                all_on = False
                break
        if all_on:
            on_pattern += 1
    print(on_pattern)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    N, M = read_int_array()
    bulbs = [None]*M
    for i in range(M):
        k, *switches = read_int_array()
        bulbs[i] = switches
    P = read_int_array()
    switches = []
    ans = 0
    def build(i):
        nonlocal ans
        if i == N:
            if all(sum(switches[x-1] for x in bulbs[i]) % 2 == P[i] for i in range(M)):
                ans += 1
        else:
            switches.append(False)
            build(i+1)
            switches[-1] = True
            build(i+1)
            switches.pop()
    build(0)
    write(ans)

main()

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

num = 0
P = list(map(int, input().split()))
for i in range(1 << N):
    tmp = [0] * M
    for j in range(N):
        if i & 1 << j:
            for l in range(M):
                if j + 1 in K[l]:
                    tmp[l] += 1

    for j in range(M):
        if tmp[j] % 2 != P[j]:
            break
    else:
        num += 1

print(num)

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

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

ans = 0
for i in range(2 ** N):
  for arr, p in zip(arrs, ps):
    odd = False
    for a in arr:
      if i & 1<<(a-1):
        odd = not odd
    if int(odd) != p:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  flag=True
  f=format(i,'b')
  if len(f)<n:
    f='0'*(n-len(f))+f
  for j in range(m):
    tmp=arr[j][1:]
    cnt=0
    for k in range(len(tmp)):
      if f[tmp[k]-1]=='1':
        cnt+=1
    cnt=cnt%2
    if p[j]!=cnt:
      flag=False
  if flag==True:
    ans+=1
print(ans)

Solution (Python):


import sys
import math

import array
import bisect
import collections
from collections import Counter, defaultdict
import fractions
import heapq
import re

sys.setrecursionlimit(1000000)


def array2d(dim1, dim2, init=None):
    return [[init for _ in range(dim2)] for _ in range(dim1)]

def argsort(l, reverse=False):
    return sorted(range(len(l)), key=lambda i: l[i], reverse=reverse)

def argmin(l):
    return l.index(min(l))

def YESNO(ans, yes="YES", no="NO"):
    print([no, yes][ans])

II = lambda: int(input())
MI = lambda: map(int, input().split())
MIL = lambda: list(MI())
MIT = lambda: tuple(MI())
MIS = lambda: input().split()

def check(N, S, P, state):
    sw = [0] * len(P)
    for i in range(N):
        if (state >> i) & 1:
            for m, s in enumerate(S):
                sw[m] += i + 1 in s
    return all((sw[i] % 2 == P[i] for i in range(len(P))))


def main():
    N, M = MI()
    S = []
    for _ in range(M):
        S.append(MIT()[1:])
    P = MIT()
    ans = 0
    for state in range(2**N):
        ans += check(N, S, P, state)
    return ans


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

Solution (Python):
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()))
ans = 0
for i in range(1 << N):
    f = True
    for j in range(M):
        s = 0
        for k in ks[j][1:]:
            s += (i >> (k - 1)) & 1
        if s % 2 != p[j]:
            f = False
    if f:
        ans += 1
print(ans)

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

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):
        ANS2=0
        for s in S[m]:
            if i & (1<<(s-1))!=0:
                ANS2+=1

        
        if ANS2%2!=P[m]:
            break

    else:
        ANS+=1

print(ANS)

Solution (Python):
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)


n,m = map(int,input().split())
a = []
for i in range(m):
        a.append(list(map(int,input().split())))
p = list(map(int,input().split()))
ans = 0
for i in range(1<<n):
        on = [0]*n
        for j in range(n):
                if i& 1<<j:
                        on[j] = 1
        for j in range(m):
                check = 0
                for k in range(1,a[j][0]+1):
                        check += on[a[j][k]-1]
                check %=2
                if check != p[j]:
                        break
        else:
                ans += 1
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)


def main():
    n,m = LI()
    aa = [set(LI_()[1:]) for _ in range(m)]
    p = LI()
    r = 0
    for i in range(2**n):
        t = [0] * m
        for j in range(n):
            if 2**j & i:
                for k in range(m):
                    if j in aa[k]:
                        t[k] ^= 1
        if p == t:
            r += 1

    return r


print(main())

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    a,p = LI()
    print((a*3+p)//2)
    return


def B():
    n = I()
    s = [None for i in range(n)]
    for i in range(n):
        l = input().split()
        s[i] = l+[i]
    s.sort(key = lambda x:(x[0],-int(x[1])))
    for i,a,b in s:
        print(b+1)
    return


def C():
    def dfs(d,k):
        if d == n:
            l.append(k)
        else:
            dfs(d+1,k+[0])
            dfs(d+1,k+[1])
    n,m = LI()
    l = []
    dfs(0,[])
    qu = LIR(m)
    p = LI()
    ans = 0
    for k in l:
        s = 0
        for q in range(m):
            num = qu[q][0]
            lis = list(map(lambda x:x-1, qu[q][1:]))
            su = 0
            for i in lis:
                su ^= k[i]
            if su == p[q]:
                s += 1
        if s == m:
            ans += 1
    print(ans)
    return


def D():
    n = I()

    return


def E():
    n = I()

    return


def F():
    n = I()

    return


if __name__ == "__main__":
    C()

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

bulbs = []

for i in range(m):
    l = input().split()
    arr = [int(x)-1 for x in l][1:]
    bulbs.append(arr)

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

import itertools

combos = 0

def test(lis):
    for i in range(m):
        need = needs[i]
        curr = 0
        for j in bulbs[i]:
            if lis[j] == 1:
                curr += 1
        if curr % 2 != need:
            return False
    return True

for i in itertools.product([0, 1], repeat=n):
    if test(list(i)):
        combos += 1

print(combos)

Solution (Python):
import itertools
N,M=map(int,input().split())
s=[[int(i)-1 for i in input().split()][1:] for i in range(M)]
k=[len(i) for i in s]
p=[int(i) for i in input().split()]
t=[[] for i in range(N)]
for i in range(M):
    for j in s[i]:
        t[j].append(i)
ans=0
for seq in itertools.product([0,1],repeat=N):
    q=[0 for i in range(M)]
    for i in range(N):
        if seq[i]==1:
            for j in t[i]:
                q[j]^=1
    flag=1
    for i in range(M):
        if p[i]!=q[i]:
            flag=0
            break
    if flag:
        ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
S=[]
for _ in range(m):
    s=list(map(int,input().split()))
    S.append(s[1:])
P=tuple(map(int,input().split()))
ans=0
for i in range(1<<n):
    for j in range(m):
        cnt=0
        for k in S[j]:
            if i&(1<<(k-1)):
                cnt+=1
        if cnt%2!=P[j]:
            break
    else:
        ans+=1
print(ans)

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

res = 0
for i in range(2 ** n):
        l = []
        for j in range(n):
                l.append(int((i & (2 ** j)) == 0))
        flag = True

        for ll, j in enumerate(k):
                cnt = 0
                for q in j:
                        cnt += l[q - 1]
                if cnt % 2 != p[ll]:
                        flag = False

        if flag:
                res += 1
print(res)

Solution (Python):
import sys

n, m = list(map(int, input().split()))
swi = []
for _ in range(m):
    k, *sss = list(map(int, input().split()))
    t = 0
    for s in sss:
        t += 1 << (s - 1)
    swi.append(t)
ppp = list(map(int, input().split()))

ans = 0
for i in range(1 << n):
    for s, p in zip(swi, ppp):
        t = i & s
        c = bin(t).count('1') % 2
        if c != p:
            break
    else:
        ans += 1
print(ans)