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

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

def on(l):
    for i in range(m):
        _s = s[i]
        cnt = 0
        for j in _s:
            cnt += l[j-1]
        if not cnt%2==p[i]:
            return 0
    return 1

from itertools import product

ans = 0
for x in product([0, 1], repeat=n):
    ans += on(x)

print(ans)

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

def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(m):
      a = list(int(i) for i in input().split())
      query.append(a)
  p = list(int(i) for i in input().split())
  
  
  A = []
  for i in range(n):
    A.append(i+1)
    
  ans = 0
  
  for i in range(1 << n):
    flag = 1
    output = []
    for j in range(n):
     if ((i >> j) & 1) == 1:
       output.append(A[j])

    for s in range(m): 
     if len(query)==0: 
      if not p[s] == 0:
        flag = 0
        break
     a = query[s]
     times = a[0]
     thischeck = 0
     for k in range(times):
       checker = a[k+1]

       if checker in output:
        thischeck += 1
       else:
        thischeck += 0
     if p[s] == thischeck%2:
       pass
     else:
       flag = 0
       break
  
    if flag:
      
      ans += 1
    else:
      pass
  print(ans)
solve()

Solution (Python):













from itertools import combinations 
from itertools import permutations 
from collections import deque 
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)
def gcds(a):
    if len(a)==1:
        return a[0]
    else:
        element = gcd(a[0], a[1])
        if len(a)==2:return(element)
        else:
            for i in range(2,n):
                element=gcd(element,a[i])
            return(element)
def debug_print(word,a,is_test=False):
    if is_test and not word:
        print("")
    elif is_test:
        print(word,a)
    else:
        pass

is_test = False
if is_test:
    n,m = [2, 2]
    smk_ = [[2, 1, 2],[1, 2]]
    pm = [0, 1]
else:        
    n,m = map(int,input().split())
    smk_ = [[int(i) for i in input().split()] for j in range(m)]
    pm = [int(i) for i in input().split()]

subsets=[]

for i in range(n):
    for c in combinations(range(n), i+1):
        subsets.append(c)
debug_print("subsets",subsets,is_test)

ans = 0
for subset in subsets:
    for i_m, sk_ in enumerate(smk_):
        counter = 0
        for sub in subset:
            debug_print("sub",sub,is_test)
            debug_print("sk_[1:]",sk_[1:],is_test)
            debug_print("pm[i_m]",pm[i_m],is_test)
            if sub + 1 in sk_[1:]:
                counter += 1
                debug_print("counter",counter,is_test)
            debug_print("","",is_test)
        if counter % 2 != pm[i_m]:
            debug_print("break: i_m=",i_m,is_test)
            break
    else:
        ans += 1


if not(any(pm)):
    ans += 1

print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    switchs = []
    for i in range(M):
        tmp = [int(x) for x in input().split()]
        switchs.append(tmp[1:])

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

    pattern = 0
    for i in range(2 ** N):
        on_state = [0] * N
        for j in range(N):
            if ((i >> j) & 1):
                on_state[(N-1) -j] = 1

        light_on = False
        for k_ in range(M):
            on_light_cnt = 0
            for switch in switchs[k_]:
                if on_state[switch-1] == 1:
                    on_light_cnt += 1

            if on_light_cnt % 2 != p[k_]:
                light_on = False
                break

            light_on = True

        if light_on == True and k_ == M-1:
            pattern += 1

    print(pattern)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np
N, M =map(int,input().split())
coeff = np.zeros((M,N)) 
for i in range(M):
    input_list = list(map(int, input().split())) 
    for j in input_list[1:]: 
        coeff[i][j-1] = 1 
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    vec = [int(num) for num in bin(i)[2:]] 
    fill = N - len(vec)
    vec = np.append(np.zeros(fill), np.array(vec)) 
    if(all(np.dot(coeff, vec) % 2 == p)):
        ans += 1
print(ans)

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

n, m = lmi()
s = [lmi() for i in range(m)]
p = lmi()
on = [0] * n
ans = 0
for i in range(1 << n):
    for j in range(n):
        on[j] = i%2
        i = i >> 1

    c = 0
    for j in range(m):
        wa = sum([on[x] for x in range(n) if x+1 in s[j][1:]])
        if wa%2 == p[j]:
            c += 1

    if c == m:
        ans += 1

print(ans)

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

switch = range(1,N+1)
pattern = [()]
for i in range(1,N+1):
    pattern.extend(tuple(itertools.combinations(switch, i)))
count = 0
for swp in pattern:
    for p, s in zip(P,S):
        match = len(set(s) & set(swp))
        if match % 2 != p:
            break
    else:
        count += 1
print(count)

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

for i in range(2**n):
    s=[]
    for j in range(n):
        s.append((i>>j)%2)
    
    if all([sum([s[y-1] for y in a[j]])%2==p[j] for j in range(m)]):
        ans+=1

print(ans)

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



ans = 0
for i in range(2**N):
    switch_str = bin(i)[2:].zfill(N)
    
    for m in range(M):
        count = 0
        for k in k_array[m]:
            if switch_str[k - 1] == "1":
                count += 1
        if count % 2 != p_array[m]:
            break
    else:
        ans += 1
print(ans)

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

KS = []
ans = 0

for i in range(2**N):

    for j in range(M):
        Z = [0]*N
        bin_s = 0
        KS = KS_lis[j]
        K = KS[0]
        S = KS[1:]

        for l in range(K):
            bin_s += 2**(int(S[l])-1)

        if bin(i & bin_s).count("1") % 2 != P[j]:
            break
    else:
        ans += 1

print(ans)

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

result = 0

def check(i, j):
    x = sum((i >> (s - 1)) & 1 for s in KS[j][1:])
    return x % 2 == p[j]

for i in range(2**N):
    result += all(check(i, j) for j in range(M))

print(result)

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

for i in range(2**n):
    res+=1
    for j in range(len(arr)):
        on = 0
        for k in range(arr[j][0]):
            on += (i>>(arr[j][k+1]-1))%2
        if (on%2 != p[j]):
            res -=1
            break
print (res)

Solution (Python):
import sys
READ = lambda : sys.stdin.readline().strip().split()
READi = lambda : map(int, sys.stdin.readline().strip().split())

N, M = READi()
LINES = []
for i in xrange(M):
  LINES += [READi()]
P = READi()

count = 0
for i in xrange(2**N):
  bits = [(i>>b)&1 for b in xrange(N)]
  ok = True
  for line, p in zip(LINES, P):
    tmp = map(lambda x: bits[x-1], line[1:])
    ok &= (sum(tmp)%2) == p
  count += int(ok)
print count

Solution (Python):

import sys

import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *
from itertools import permutations
readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

n, m = readmi()
sw = []
count = 0
d = defaultdict(int)

for i in range(m):
    p = readl()
    sw.append(p[1:])
p = readl()
count = 0
for i in range(2 ** n):
    den = defaultdict(int)
    for j in range(n):
        if (i >> j) & 1:
            for k in range(m):
                if j + 1 in sw[k]:
                    den[k] += 1
    flg = True
    for j in range(m):
        if den[j] % 2 != p[j]:
            flg = False
    if flg:
        count += 1
print(count)

Solution (Python):

"""
Created on Mon May 27 22:13:19 2019

@author: Yamazaki Kenichi
"""

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

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for bit in range(1<<N):
    now = [0 for i in range(M)]
    for i in range(N):
        if bit & 1<<i:
            for j in range(M):
                now[j] += S[j]//(1<<i)
    flg = True
    for j in range(M):
        if now[j]%2 != p[j]:
            flg = False
    ans += flg
print(ans)

Solution (Python):

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0

for bit in range(2 ** N):
    flag = False
    
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            
            if (1 << (s - 1)) & bit:
                cnt += 1
        
        if cnt % 2 == p[m]:
            continue
        
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

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

def is_light(sw, p, state):
    acc = 0
    for s in sw:
        if ((state >> (s-1))& 1) == 1:
            acc += 1
    return acc % 2 == p


ans = 0
for i in range(1<<n):
    for j in range(m):
        if not is_light(ss[j], p[j], i):
            break
    else:
        ans += 1
print(ans)

Solution (Python):

"""
Created on Mon May 27 21:28:42 2019

@author: Yamazaki Kenichi
"""

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

S = [0 for i in range(M)]
for i in range(M):
    for j in range(1,ks[i][0]+1):
        S[i] += 2**(ks[i][j]-1)

ans = 0
for i in range(2**N):
    flg = True
    for j in range(M):
        if ('{:010b}'.format(S[j]&i)).count('1') % 2 == p[j]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

Solution (Python):

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0

for bit in range(2 ** N):
    flag = False
    
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            
            if (1 << (s - 1)) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Solution (Python):

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0

for bit in range(2 ** N):
    flag = False
    
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            if (1 << (s - 1)) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

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

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

p = list(map(int, input().split()))
    
cnt = 0
    
for i in range(2**n):
    bin_i = "{:010b}".format(i)[::-1]
    
    for j in range(m):
        ks = kss[j]
        k = ks[0]
        s = ks[1:]
        
        sum_s = 0
        
        for x in range(k):
            sum_s += int(bin_i[s[x]-1])
            
        if sum_s % 2 != p[j]:
            break
    else:
        cnt += 1
        
print(cnt)

Solution (Python):
import numpy as np

N, M = map(int, input().split())
connect = []
for j in range(M):
    connect.append(list(map(int, input().split())))
plist = list(map(int, input().split()))

count = 0
for n in range(2**N):
  for j in range(M):
    connect_score = sum(2**(np.array(connect[j][1:])-1))
    switch_on = n & connect_score
    num_switch_on = [int(k) for k in str(bin(switch_on))[2:]]
    if (sum(np.array(num_switch_on)) % 2) != plist[j]:
  		 break
    if j == M-1:
        count += 1
  
print(count)

Solution (Python):

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


sw = []
for i in range(M):
    k, *s = map(int, input().split())
    sw.append(s)


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


ans = 0
for bit in range(2 ** N):
    flag = False
    for m in range(M):
        cnt = 0
        for s in sw[m]:
            if 1 << (s - 1) & bit:
                cnt += 1
        if cnt % 2 == p[m]:
            continue
        else:
            flag = True
            break
    if not flag:
        ans += 1


print(ans)

Solution (Python):

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


lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a]

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




ans = 0 
for i in range(2 ** N): 
    
    a = format(i, '012b')
    
    lst2 = list(a[2:]) 
    
    
    flag = True 
    l = 0 
    for j in lst: 
        
        count = 0 
        for k in j[1:]: 
            
            if lst2[9-k+1] == '1': 
                count += 1
                
        
        
        if count%2 != p[l]: 
            flag = False 
            
        l += 1 
    if flag: 
        ans += 1
        

print (ans)

Solution (Python):
n,m = map(int,input().split())
res = 0
Q = []
for i in range(m):
    Q.append(list(map(int,input().split()))[1:])
P = list(map(int,input().split()))

for s in range(1<<n):
    tmp = 0
    for i in range(len(Q)):
        cnt = 0
        for t in Q[i]:
            if s>>(t-1) &1 == 1:
                cnt += 1
        if cnt % 2 == P[i]:
            tmp += 1
    if tmp == m:
        res += 1
print(res)

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

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


ans = 0
for i in range(2 ** N): 
    a = format(i, '012b')
    lst2 = list(a[2:])
    
    flag = True
    l = 0
    for j in lst:
        
        count = 0
        for k in j[1:]:
            
            if lst2[9-k+1] == '1': 
                count += 1
                
        
        
        if count%2 != p[l]:
            flag = False
            
        l += 1
    if flag:
        ans += 1
        
    

print (ans)

Solution (Python):
n,m=map(int,input().split())
k=[]
for i in range(m):
    k.append(list(map(int,input().split()))[1:])
p=list(map(int,input().split()))
a=0
for i in range(2**n):
    i=list(map(int,list(bin(i)[2:].zfill(n))))
    for j in range(m):
        x=p[j]
        for l in k[j]:
            x^=i[l-1]
        if x==1:break
    else:a+=1
print(a)

Solution (Python):

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

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


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

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

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

ss = np.array(list(map(int,input().split())))

def ans(n):
    return(b1(n,np.zeros(m))+b0(n,np.zeros(m)))

def b0(n,t):
    global ss
    if n == 0:
        return 0
    return b0(n-1,t)+b1(n-1,t)

def b1(n,t):
    global ks
    global ss
    t = t + np.array([int(n in k) for k in ks])
    if n == 0:
        return all([i%2==s for i,s in zip(t,ss)])
    return b0(n-1,t)+b1(n-1,t)

print(ans(n))

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

def is_on(n, idx):
    bin_string = str(bin(n)[2:]).zfill(N)
    return bin_string[idx - 1]

num = 0
for n in range(2 ** N):
    all_flag = True
    for p, lis in zip(p_list, lists):
        flag = (sum([is_on(n, l) == '1' for l in lis]) % 2) == p
        all_flag = all_flag & flag
    num += all_flag
print(num)

Solution (Python):
n,m = map(int,input().split())
x = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
    bag = []
    cnt = 0
    for j in range(n):  
        if ((i >> j) & 1):  
            bag.append(True)
        else:
            bag.append(False)
    for l in range(m):
        res = 0
        for h in x[l][1:]:
            if bag[h-1]:
                res += 1
        if res%2!=p[l]:
            break
        else:
            cnt += 1
    if cnt==m:
        ans += 1
print(ans)

Solution (Python):



def make_switch_pattern(N, M):
    for i in range(2**N):
        tmp_lst = [0]*N
        for j in range(N):
            tmp_lst[j] = i % 2
            i = int(i/2)
        tmp_lst.reverse()
        switch_pattern = tuple(tmp_lst)
        yield switch_pattern


def all_light_41_pi(switch_pattern, light_lst, pi_lst):
    for i in range(len(light_lst)):
        switches = light_lst[i]
        pi = pi_lst[i]
        on_count = 0
        for k in switches:
            if switch_pattern[k-1] == 1:
                on_count += 1
        on_count %= 2
        if on_count != pi:   
            return False
    return True


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

light_lst = []  
for i in range(M):
    tmp_lst = list(map(int, input().split()))
    tmp_tple = tuple(tmp_lst[1:])
    light_lst.append(tmp_tple)

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

count = 0
for switch_pattern in make_switch_pattern(N, M):
    if all_light_41_pi(switch_pattern, light_lst, pi_lst):
        count += 1

print(count)

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

ps = list(map(int,input().split()))
ans = 0
for i in range(2**N):
    f = True
    for k, p in zip(ks,ps):
        o =  0
        for j in k:
            if (i >> j-1)&1:
                o += 1
        if o%2 != p:
            f = False

    if f :
        ans += 1
print(ans)

Solution (Python):
from itertools import product
N, M = map( int, input().split())
K = [ list( map( int, input().split())) for _ in range(M)]
P = list( map( int, input().split()))
ans = 0
for p in product( range(2), repeat = N):
    t = 1
    for i in range(M):
        cnt = 0
        for j in range(1, K[i][0]+1):
            if p[K[i][j]-1] == 1:
                cnt += 1
        if cnt%2 != P[i]:
            t = 0
            break
    if t == 1:
        ans += 1
print( ans)

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

ans = 0

for i in range(2 ** n):
  pat = []
  t = 0
  for j in range(n):
    if (i >> j) & 1:
      pat.append(True)
    else:
      pat.append(False)
  for k in range(m):
    cnt = 0
    for l in s[k][1:]:
      if pat[l-1]:
        cnt += 1
    if cnt % 2 == p[k]:
      t += 1
  if t == m:
    ans += 1
    
print(ans)

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

ans=0

for i in range(2**n):
    pat=[]
    t=0
    for j in range(n):
        if (i>>j)&1:
            pat.append(True)
        else:
            pat.append(False)
    for k in range(m):
        cnt=0
        for l in s[k][1:]:
            if pat[l-1]:
                cnt+=1
        if cnt%2==p[k]:
            t+=1
    if t==m:
        ans+=1

print(ans)

Solution (Python):
N, M = map(int, input().split())
lists = []
for _ in range(M):
    lists.append(list(map(int, input().split()))[1:])
p_list = list(map(int, input().split()))
num = 0
len_m = N
for n in range(2 ** N):
    flag = True
    for p, lis in zip(p_list, lists):
        flag = int(flag) * int((sum([str(bin(n)[2:]).zfill(len_m)[l - 1] == '1' for l in lis]) % 2) == p)
    num += flag
print(num)

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

ans = 0
for pattern in range(2**N):
    p = []
    for keta in range(N):
        if pattern & (1<<keta) > 0:
            p.append(1)
        else:
            p.append(0)
    

    for m in range(M):
        cnt = 0
        for si in s[m]:
            cnt += p[si]
        
        if cnt%2 != c[m]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import product


def count(ss, ns, ps):
    for i, s in enumerate(ss):
        sum_s = sum([ns[_s - 1] for _s in s])
        if sum_s % 2 != ps[i]:
            return 0
    return 1


n, m = list(map(int, input().split(" ")))
ks = []
ss = []
for _ in range(m):
    k, *s = list(map(int, input().split(" ")))
    ks.append(k)
    ss.append(s)
ps = list(map(int, input().split(" ")))

ns_list = list(product([0, 1], repeat=n))
ans = 0
for ns in ns_list:
    ans += count(ss, ns, ps)
print(ans)

Solution (Python):
import numpy as np

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

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

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

ans = 0
for i in range(2**n):
    i = list(reversed("{:010b}".format(i)))
    f = True
    for k,s in zip(ks,ss):
        o = 0
        for j in k:
            if i[j-1] == "1":
                o+=1
        if o%2 != s:
            f = False
    if f:
        ans+=1
print(ans)

Solution (Python):
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=[(t>>s)&1 for s in range(N)]
    light=True
    for i in range(M):
        cnt=0
        for j in range(len(l[i])):
            if tmp[l[i][j]-1]==1:
                cnt+=1
        if cnt%2 != p[i]%2:
            light=False
    if light:
        ans+=1

print(ans)

Solution (Python):


def switch_on_off(n, keta):
    bin_str = format(n, '0{}b'.format(keta))
    return list(bin_str)

def check_light(n, N, s, index, P):
    switch = switch_on_off(n, N)
    sum = 0
    for v in s:
        sum += int(switch[int(v) - 1])
    if sum % 2 == P[index]:
        return 1
    return 0

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


ans = 0
for n in range(2 ** N):
    sum = 0
    for index, s in enumerate(S):
        sum += check_light(n, N, s, index, P)
    if sum == M:
        ans += 1

print(ans)

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

S = []
for i in range(M) :
    L = list(map(int,input().split()))[1:]
    for j in range(len(L)) :
        L[j] -= 1
    S.append(L)

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

ans = 0

for bit in range(1 << N) :
    A = []
    for k in range(N) :
        if bit & (1 << k) :
            A.append(k)
    for i in range(len(S)) :
        cnt = 0
        for s in S[i] :
            if s in A :
                cnt += 1
        if (cnt % 2) != P[i] :
            break
    else :
        ans += 1
print(ans)

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

for bn in range(2**n):
        bn = str(bin(bn))[2:].zfill(n)
        bright = 0
        for i in range(m):
                p_exp = 0
                for j in range(n):
                        
                        if (j+1 in s[i]) and (bn[j] == '1'): p_exp += 1
                if p_exp%2 == p[i]: bright += 1
                
        
        if bright == m: ans += 1
print(ans)

Solution (Python):

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


def convert(x):
    li=[]
    for i in range(1,n+1):
        li.append(x%2)
        x=x//2
    return li
ans=0
for i in range(2**n):
    sw=convert(i)
    flg=True
    for j in range(m):
        lit=p[j]
        for k in con[j]:
            if sw[k-1]==1:
                if lit==1:
                    lit=0
                else:
                    lit=1
        if lit==1:
            flg=False
            break
    if flg:
        ans+=1
print(ans)

Solution (Python):
import numpy as np
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M = IL()
K = [IL()[1:] for i in range(M)]
p = np.array(IL())

switch = np.array([[0]*M for i in range(N)])
for i in range(M):
    while K[i]:
        num = K[i].pop()
        switch[num-1][i] = 1

ans = 0
for i in range(1 << N):
    cnt = np.array([0]*M)
    for j in range(N):
        if ((i >> j) & 1) == 1:
            cnt += switch[j]
    else:
        if (p == (cnt%2)).all():
            ans += 1
print(ans)

Solution (Python):



from sys import stdin


def bit_count(x):
    return bin(x).count("1")

def bit_exchange(x):
    return 2 ** (x-1)

all_switch_list=[]
clear_list=[]


N, M = [int(x) for x in stdin.readline().rstrip().split()]

for i in range(M):
    switch_list = [int(x) for x in stdin.readline().rstrip().split()]
    bin_s_list = 0
    for j in range(switch_list[0]):
        
        bin_s_list = bin_s_list | bit_exchange(switch_list[j+1])

    
    all_switch_list.append(bin_s_list)
remainder = [int(x) for x in stdin.readline().rstrip().split()]



clear_list = list(range(bit_exchange(N+1)))
for i in range(M):
    for j in range(bit_exchange(N+1)):
        count = j & all_switch_list[i]
        if bit_count(count) % 2 != remainder[i]:
            try:
                clear_list.remove(j)
            except:
                pass

print(len(clear_list))

Solution (Python):
N, M = map(int, input().split())
switches = []
for i in range(M):
    _, *switch = map(int, input().split())
    switches.append(switch)
condition = [int(x) for x in input().split()]
cnt = 0
for status in range(2 ** N):
    satisfied = False
    for i, switch in enumerate(switches):
        total_status = sum([1 & (status >> (s - 1)) for s in switch])
        if condition[i] != total_status % 2: break
        elif i == len(switches) - 1: satisfied = True
    if satisfied: cnt += 1
print(cnt)

Solution (Python):

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

s_list=[]
for i in range(M):
    s_list.append(list(map(int, input().split())))
    
bit_list =[]
for i in range(2**N):
    bit_list.append(bin(i)[2:].zfill(N))
p_list = list(map(int, input().split()))

delete_list = []
for i in range(M):
    count = 0
    for j in range(2**N):
        count = 0
        for k in range(s_list[i][0]):
            if int(bit_list[j][s_list[i][k+1]-1]) == 1:
                count +=1
        if count % 2 != p_list[i]:
            delete_list.append(bit_list[j])
bit_list =[i for i in bit_list if i not in delete_list]
print(len(bit_list))

Solution (Python):
N,M=list(map(int,input().split()))
ks=[]
for m in range(M):
    k,*s=list(map(int,input().split()))
    ks.append(s)
pm=list(map(int,input().split()))
ct=0
for i in range(2**N):
    bf="{:010b}".format(i)[::-1]
    allok=True
    for m in range(M):
        if not allok:break
        sm=0
        for s in ks[m]:
            sm+=int(bf[s-1])
        if sm%2!=pm[m]:
            allok=False
            break
    if allok:
        ct+=1
print(ct)

Solution (Python):
n,m=(int(i) for i in input().split())
b=[]
v=[]
for i in range(m):
  a=[]
  for j in input().split():
    a.append(int(j))
  b.append(a[1:])
for j in input().split():
  v.append(int(j))
r=0
for i in range(2**n):
  c=i
  t=[0 for l in range(m)]
  for j in range(n):
    if c-(c//2)*2==1:
      for k in range(m):
        if j+1 in b[k]:
          t[k]=(t[k]-1)**2
    c=c//2
  if t==v:
    r=r+1
print(r)

Solution (Python):
import itertools

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


def main():
	k = []
	s = []
	answers = []

	for i in range(M + 1):
		inputs = list(map(int,input().split()))
		if i == M:
			answers = inputs.copy()
		else:
			k.append(inputs[0])
			s.append(inputs[1:])

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

	result = []
	for c in allCandidates:
		ok = True
		for i, ss in enumerate(s):
			sumBulk = 0
			for sNumber in ss:
				sumBulk += c[sNumber - 1]
			if sumBulk % 2 != answers[i]:
				ok = False
		if ok:
			result.append(c)

	print(len(list(set(result))))

if __name__ == '__main__':
	main()