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

Solution (Python):
import 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):
def sum(A):
    a=0
    for num in range(len(A)):
        a=a+A[num]
    return a
             


N,M=input().split()
N=int(N)
M=int(M)
K=[100]*(M+1)
for num in range(M+1):
    K[num]=input().split()
    for num2 in range(len(K[num])):
        K[num][num2]=int(K[num][num2])

a=[0]*N
cnt=0
for num in range(pow(2,N)):
    flag=0
    n=num
    i=0
    while(N>i):
        a[N-1-i]=n//pow(2,N-1-i)
        if(a[N-1-i]==1):
            n=n-pow(2,N-1-i)
        i=i+1
    for num2 in range(M):
        b=0
        for num3 in range(len(K[num2])-1):
            b=b+a[K[num2][num3+1]-1]
        if(b%2!=K[M][num2]):
            flag=1
    if(flag==0):
        cnt=cnt+1
print(cnt)

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

for i in range(2 ** n):
    on_off = [0] * n
    for j in range(n):
        if i >> j & 1:
            on_off[j] = 1
    
    for j in range(m):
        cnt = 0
        
        for k in bulbs[j][1:]:
            cnt += on_off[k - 1]
        
        if cnt % 2 != p[j]:
            cmb[i] = 0
            
print(sum(cmb))

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

num = 2 ** N
result = 0

for i in range(num):
    flag = True
    pattern = bin(i)[2:]
    pattern = '0' * (N-len(pattern)) + pattern

    for j in range(M):
        sw = 0
        for k in range(ks[j][0]):
            if pattern[ks[j][k+1]-1] == '1':
                sw += 1

        if sw % 2 != p[j]:
            flag = False
            break

    if flag:
        result += 1

print(result)

Solution (Python):
n,m = map(int,input().split())
mask = [0]*m
ans = 0

for i in range(m):
  for j in [int(w) for w in input().split()][1:]:
    mask[i] += (1 << j-1)
p = [1 ^ int(i) for i in input().split()]

for i in range(1 << n):
  cnt = 0
  for j in range(m):
    temp = i & mask[j]
    flag = p[j]
    for k in range(n):
      flag ^= (temp >> k) & 1
    if flag:
      cnt += 1
  if cnt == m:
    ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
ks_array = [[int(x) for x in input().split()] for y in range(m)]
p_array = [int(x) for x in input().split()]
k_array = [x[0] for x in ks_array]
s_array = [x[1:] for x in ks_array]

comb = 2 ** n
cnt = 0
for i in range(comb):
    now = [False for x in range(n)]
    bit = bin(i)
    for index in range(n):
        if bin(i >> index)[-1] == "1":
            now[index] = True

    flag = True
    for index, ss in enumerate(s_array):
        tmp = 0
        for s in ss:
            if now[s-1]:
                tmp += 1
        if tmp % 2 != p_array[index]:
            flag = False
    if flag:
        cnt += 1
print(cnt)

Solution (Python):
import copy

n, m = map(int, input().split())
ks_ls = []
count = 0
while count < m:
    ks_ls.append(list(map(int, input().split())))
    count = count + 1
p_ls = list(map(int, input().split()))

all_pattern = []
hoge = [0]
hoge2 = [1]
all_pattern.append(hoge)
all_pattern.append(hoge2)
count2 = 0
while count2 < n-1:
    temp = []
    for s in all_pattern:
        hoge3 = s
        hoge4 = copy.deepcopy(s)
        hoge3.append(0)
        hoge4.append(1)
        temp.append(hoge3)
        temp.append(hoge4)
    count2 = count2 + 1
    all_pattern = temp
result = []
for i in all_pattern:
    ok_flg = True
    for index2, j in enumerate(ks_ls):
        sum = 0
        for index, k in enumerate(j):
            if index == 0:
              continue
            sum = sum + i[k-1]
        if sum%2 != p_ls[index2]:
            ok_flg = False
    if ok_flg :
        result.append(i)
print(len(result))

Solution (Python):
from itertools import product

n, m = map(int, input().split())
masks = [0] * n
for i in range(m):
    _, *ss = map(int, input().split())
    for s in ss:
        masks[s - 1] |= 1 << i
init = int(''.join(input().strip().split())[::-1], base=2)

def gray(n):
    if n == 1:
        yield 0
    else:
        yield from gray(n-1)
        yield n - 1
        yield from gray(n-1)

v = init
cnt = int(not v)
for i in gray(n):
    v ^= masks[i]
    if not v:
        cnt += 1
print(cnt)

Solution (Python):
n,m = map(int,input().split())
li = []
for mi in range(m):
  tmp = list(map(int,input().split()))[1:]
  lli = [0]*n
  for ni in range(n):
    if (ni+1) in tmp:
      lli[ni] = 1
  li += [lli]
p = list(map(int,input().split()))
yyy = [0]*n
score = 0
while True:
  must1 = 1
  for mi in range(m):
    onoff = 0
    for ni in range(n):
      onoff += li[mi][ni]*yyy[ni]
    should1 = bool(onoff%2 == p[mi])
    must1 *= should1
  if must1 == 1:
    score += 1
  yyy[0] += 1
  for ni in range(n-1):
    if yyy[ni] == 2:
      yyy[ni] = 0
      yyy[ni+1] += 1
  if yyy[n-1] == 2:
    break
print(score)

Solution (Python):


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

masks = []
for i in range(M):
    x = input().split()
    k = int(x[0])
    s = x[1:]
    m = 0
    for b in s:
        m += 2**(int(b)-1)
    masks.append(m)

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
















combinations = 0
for b in range(2**N):
    all_on = True
    for m, c in zip(masks, p):
        if bin(b&m).count("1")%2 != c:
            all_on = False
            break
    if all_on:
        combinations += 1

print(combinations)

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

all_on = 0
for sp in product([0, 1], repeat=n):
    on = 0
    
    for i in range(m):
        cnt = 0
        
        for j in range(len(s[i])):
            if sp[s[i][j] - 1] == 1:
                cnt += 1
        if cnt % 2 == p[i]:
            on += 1
    if on == m:
        all_on += 1

print(all_on)

Solution (Python):
N, M = map(int, input().split())
list1 = []
for i in range(M):
  Input = input().split()
  k = int(Input[0])
  list1.append([])
  for j in range(k):
    list1[i].append(int(Input[j + 1]))
p = list(map(int, input().split()))
sum = 0
sumsum = 0
Bool = True
for l in range(2 ** N):
  onoff = format(l, 'b')
  onoff = onoff.zfill(N)
  for m in range(M):
    for n in range(len(list1[m])):
      sum += int(onoff[list1[m][n] - 1])
    if (not sum % 2 == p[m]):
      Bool = False
    sum = 0
  if Bool:
    sumsum +=1
  Bool = True
print(sumsum)

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

ans = 0
for i in range(2**N):
    S = set([1+j for j in range(N) if 2**j & i])
    for j, k in enumerate(K):
        if len(S.intersection(k))%2 != P[j]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
from __future__ import print_function


import sys
input = sys.stdin.readline

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

def main():
    n,m = map(int, input().split()) 
    lights=[]
    for i in range(m):
        ll=list(map(int, input().split()))
        lights.append(ll[1:])
    p = list(map(int, input().split()))
    
    
    ans=0
    for case in range((1<<n)):
        
        
        ii=0
        f_flag=0
        for light in lights:
            cnt_on=0
            for i in light:
                if (case>>(i-1))&1:
                    cnt_on+=1
            
            if  cnt_on%2!=p[ii]:
                f_flag=1
            ii+=1
        if f_flag==0:
            ans+=1
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
from __future__ import print_function


import sys
input = sys.stdin.readline

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


































def main():
    n,m = map(int, input().split()) 
    lights=[]
    for i in range(m):
        ll=list(map(int, input().split()))
        lights.append(ll[1:])
    p = list(map(int, input().split()))
    eprint(lights)
    
    
    
    
    
    
    ans=0
    for case in range((1<<n)):
        eprint(bin(case))
        
        ii=0
        f_flag=0
        for light in lights:
            cnt_on=0
            for i in light:
                if (case>>(i-1))&1:
                    cnt_on+=1
            eprint(cnt_on,p[ii])
            if  cnt_on%2!=p[ii]:
                f_flag=1
            ii+=1
        if f_flag==0:
            ans+=1
    print(ans)

        
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


    
    
if __name__ == '__main__':
    main()

Solution (Python):
import itertools

N, M = map(int, input().split())
bulbs = [] * M
for i in range(M):
    bulb = list(map(int, input().split()))
    del bulb[0]
    bulbs.append(bulb)
p = list(map(int, input().split()))
seqs = list(itertools.product((0, 1), repeat=N))
for i_bulbs in range(len(bulbs)):
    target = []
    for i_seqs in range(len(seqs)):
        count = 0
        for num in bulbs[i_bulbs]:
            count += seqs[i_seqs][num - 1]
        if count % 2 != p[i_bulbs]:
            target.append(i_seqs)
    for i in reversed(target):
        del seqs[i]
    if not len(seqs):
        break
print(len(seqs))

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

ans = 0
for i in range(2**N):
    bin_i = str(bin(i))[2:].zfill(N)
    flag = True
    for m in range(M):
        mm = 0
        for n in range(len(s[m])):
            if bin_i[s[m][n]-1] == '1':
                mm += 1
        if mm % 2 == p[m]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1
        
print(ans)

Solution (Python):
n, m = map(int, input().split())
array = [[int(x) for x in input().split()] for x in range(m)]
p_array = [int(x) for x in input().split()]

s_array = [x[1:] for x in array]
k_array = [x[0] for x in array]

res = 0
bit = 2 ** n
for bit_tmp in range(bit):
    flags = [False for x in range(n)]
    light_flag = True
    for shift in range(n):
        if 1 & bit_tmp >> shift:
            flags[shift] = True
    for index, s in enumerate(s_array):
        tmp = 0
        for ss in s:
            if flags[ss - 1]:
                tmp += 1
        if tmp % 2 != p_array[index]:
            light_flag = False
    if light_flag:
        res += 1
print(res)

Solution (Python):










import numpy as np
import math
import copy

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





mask_list = [0 for _ in range(N)]

for i in range(M):
    switches = list(map(int, input().split()))

    
    for j in range(1, len(switches)):
        sw_num = (switches[j] - 1) 
        sw_bit = 1 << i 
        mask_list[sw_num] = mask_list[sw_num] | sw_bit

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

conds_dec = 0

for i in range(len(conds)):
    conds_dec |= conds[i] << i

light_num = 0
for s in range(1 << N):
    t = 0
    for i in range(N):
        if s >> i & 1:
            t = t ^ mask_list[i]
    if t == conds_dec:
        light_num += 1


print(light_num)

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

count = 0
for i in range(2 ** N):
    flg = True
    for m in range(M):
        on = 0
        for s in S[m]:
            if (i >> s - 1) & 1:
                on += 1
        if on % 2 != P[m]:
            flg = False
            break
    if flg:
        count += 1
print(count)

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

Switches = [None] + [ list([0]) for _ in range(N) ]
Ss = [list(map(lambda x: Switches[int(x)], input().split()[1:])) for _ in range(M)]
for coil, S in zip(map(int, input().split()), Ss):
    S.append([coil])

cnt = 0
for L in range(pow(2, N)):

    for i, onoff in enumerate(((L & (1 << x)) != 0 for x in range(N))):
        Switches[i+1][0] = onoff

    if sum((1 for sji in Ss if sum((1 for si in sji for siv in si if siv)) % 2 != 0 )) <= 0:
        cnt += 1

print(cnt)

Solution (Python):
import itertools

n, m = map(int, input().split())
count = 0
light = [0] * m
sw = [[] for _ in range(n)]

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

for pattern in itertools.product([0, 1], repeat=n):
    flag = True
    check = [0] * m
    for checkSW in range(n):
        if pattern[checkSW] == 1:
            for c in sw[checkSW]:
                check[c] += 1
    for q in range(m):
        if check[q] % 2 != p[q]:
            flag = False
    if flag:
        count += 1


print(count)

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

Switches = [None] + [ list([0]) for _ in range(N) ]
Ss = [list(map(lambda x: Switches[int(x)], input().split()[1:])) for _ in range(M)]
for coil, S in zip(map(int, input().split()), Ss):
    S.append([coil])

cnt = 0
for L in range(pow(2, N)):

    for i, onoff in enumerate(((L & (1 << x)) != 0 for x in range(N))):
        Switches[i+1][0] = onoff

    if sum((sum((1 for si in sji for siv in si if siv)) % 2 != 0 for sji in Ss)) <= 0:
        cnt += 1

print(cnt)

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

Switches = [None] + [ list([0]) for _ in range(N) ]
Ss = [list(map(lambda x: Switches[int(x)], input().split()[1:])) for _ in range(M)]
for coil, S in zip(map(int, input().split()), Ss):
    S.append([coil])

cnt = 0
for L in range(pow(2, N)):

    for i, onoff in enumerate(((L & (1 << x)) != 0 for x in range(N))):
        Switches[i+1][0] = onoff

    if sum((sum((1 for si in sji for siv in si if siv)) % 2 != 0 for sji in Ss)) <= 0:
        cnt += 1

print(cnt)

Solution (Python):
n, m = list(map(int, input().split()))
s = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(1<<n):
  good = True
  for j in range(m):
    cur = 0
    for e in s[j][1:]:
      if i&(1<<(e-1)):
        cur += 1
    if cur%2!=p[j]:
      good = False
      break
  if good:
    ans += 1
print(ans)

Solution (Python):
from itertools import product


N, M = map(int, input().split())
k, s = zip(
    *(
        (int(k), list(map(int, s.split())))
        for _ in range(M)
        for k, s in [input().split(maxsplit=1)]
    )
)
p = list(map(int, input().split()))


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


print(ans)

Solution (Python):
import itertools


N, M = map(int, input().split())
connected_switches = [[int(x) - 1 for x in input().split()[1:]] for x in range(M)]
conditions = list(map(int, input().split()))

ok = 0
for patterns in itertools.product((0, 1), repeat=N):
    patterns = list(patterns)
    is_lighting = True
    for i, lights in enumerate(connected_switches):
        turned_sw = sum([patterns[x] for x in lights])
        if turned_sw % 2 != conditions[i]:
            is_lighting = False
            break
    if is_lighting:
        ok += 1

print(ok)

Solution (Python):

import numpy as np

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

ks_list = []

for i in xrange(m):
	ks_list.append(map(int,raw_input().split()))



p_list = (map(int,raw_input().split()))

cordStates = [[0 for i in range(m)] for j in range(n)]

for i in xrange(m):
    for j in xrange(ks_list[i][0]):
        tmp =  ks_list[i][j+1]-1
        cordStates[tmp][i] = 1



SwStates = [[0 for i in range(n)] for j in range(2**n)]

for i in xrange(2**n):
    SwBin = format(np.left_shift(i, 0), '0'+str(n)+'b')
    SwStates[i]=list(SwBin)
    SwStates[i] = list(map(int, SwStates[i]))  



LightStates = [[0 for i in range(m)]for j in range(2**n)]


for i in xrange(1,(2**n)):
    nowStates = [0 for c in range(m)]
    
    
    for j in xrange(n):
        
        
        if SwStates[i][j]==1:
            
            for k in xrange(m):
                
                
                
                
                if (nowStates[k]^cordStates[j][k])==1:
                    
                    nowStates[k] = 1
                else:
                    
                    nowStates[k] = 0

                

        
    
    LightStates[i] = nowStates

ans = 0
for i in xrange(len(LightStates)):
    if(LightStates[i]==p_list):
        ans+=1;


print ans

Solution (Python):
from itertools import product
def resolve():
  N, M = map(int, input().split())
  k = []
  s = []
  for i in range(M):
    s.append(list(map(int, input().split())))
    k.append(s[-1].pop(0))
  p = list(map(int, input().split()))
  ret = 0
  print(sum([1 for st in product(range(2), repeat=N)
       if sum([1 for i in range(M)
               if sum([st[sij-1] for sij in s[i]])%2 == p[i]
              ]) == M
      ]))
resolve()

Solution (Python):





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

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


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






res = 0

for switch_pattern in (list(map(int, bin(i)[2:].zfill(N))) for i in range(2 ** N)):
    flg = True
    
    for bulb, ws in zip(bulb_lst, want_switch):
        if ws != sum([switch_pattern[con_idx-1] for con_idx in bulb[1:]]) % 2:
            flg = False
            break
    if flg:
        res += 1
print(res)

Solution (Python):
n,m=map(int,input().split())
l=[]
for _ in range(m):
    l.append(list(map(int,input().split())))
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    swi=[]
    for _ in range(n):
        swi.append(i%2)
        i=i//2
    all=0
    for j in range(m):
        cnt=0
        for s in range(1,l[j][0]+1):
            if swi[l[j][s]-1]==1:
                cnt+=1
        if cnt%2==p[j]:
            all+=1
    if all==m:
        ans+=1
print(ans)

Solution (Python):
n, m = map(int, input().split())
k, s = [], []
ans = 0
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()))

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

Solution (Python):






import sys

import itertools
input = sys.stdin.readline
N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M+1)]





"""
5 2
3 1 2 5
2 2 3
1 0
"""












cnt = 0

for on in itertools.product(range(0, 2), repeat=N):
    for i in range(M):
        sum_ = 0
        for j in range(l[i][0]):
            ind = l[i][j+1]-1
            sum_ += on[ind]
        if sum_%2 != l[-1][i]:
            break
    else:
        cnt += 1
print(cnt)

"""
s = range(N)
cnt = 0

for e in range(1, N+1):
    c = list(itertools.combinations(s,e))
    o = list(range(N))
    for b in c:
        
        a = np.zeros((N))
        for d in b:
            a[d] = 1
        
        for i in range(M):
            sum_ = 0
            for j in range(l[i][0]):
                ind = l[i][j+1]-1
                
                sum_ += a[ind]
            o[i] = sum_%2==l[-1][i]
        if np.all(o):
            cnt += 1

o = list(range(N))
a = np.zeros((N))
for i in range(M):
    sum_ = 0
    for j in range(l[i][0]):
        ind = l[i][j+1]-1
        sum_ += a[ind]
    o[i] = sum_%2==l[-1][i]
if np.all(o):
    cnt += 1
print(cnt)
"""





"""
2 2
2 1 2
1 2
0 1
"""

Solution (Python):
N, M = map(int, input().split())
S_lists = [list(map(int, input().split()))[1:] for _ in range(M)]
P = list(map(int, input().split()))
count = 0
for n in range(2**N):
  l = 1
  for p, S in zip(P, S_lists):
    l *= (sum([int(bin(n)[2:].zfill(N)[s-1]) for s in S]) % 2 == p)
  count += l
print(count)

Solution (Python):
n,m=map(int,input().split())
a=[[0 for h in range(n)] for i in range(2**n)]
b1=[[0 for i in range(m)] for h in range(2**n)]

for i in range(2**n):
  b=i
  for j in range(n):
    c=b//(2**(n-j-1))
    a[i][j]+=c
    b-=c*(2**(n-j-1))

for i in range(m):
  lights=list(map(int,input().split()))
  for j in range(2**n):
    for h in range(len(lights)-1):
      b1[j][i]+=a[j][lights[h+1]-1]
check=list(map(int,input().split()))

ans=0
for i in range(2**n):
  flag=0
  for j in range(m):
    if b1[i][j]%2 != check[j]:
      flag=1
      break
  if flag==0:
    ans+=1
print(ans)

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
sw = []
ki = []
counter = 0
for i in range(m):
    inp = list(map(int, input().split()))
    sw.append(inp[1:])
    ki.append(inp[0])
criterion = list(map(int, input().split()))
for switch in range(2**n):
    flash = defaultdict(int)     
    for j in range(n):
        if ((switch >> j) & 1):
            for light in range(m):  
                if (j + 1) in sw[light]:
                    flash[light] += 1
    token = True
    for l in range(m):
        if (flash[l] + criterion[l]) % 2 == 1:
            token = False
    if token:
        counter+= 1
print(counter)

Solution (Python):

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

pat = [ format(i, '0'+ str(N) + 'b') for i in range(pow(2, N))]
count = 0

for p in pat:

    breaked = False
    for i in range(M):
        cnt = 0

        for s in Ks[i][1:]:

            if p[s-1] == '1':
                cnt += 1

        if cnt % 2 != P[i]:
            breaked = True

            break
    if not breaked:
        count += 1

        
print(count)

Solution (Python):
def add(s,d):
     sum=0
     for i in d[1:]:
          sum+=s[i] 
     return sum

def check(m):
    for i in range(m):
        if add(s, d[i]) % 2 == p[i]:
            pass
        else :
            return -1
    return 1
        
        
d = []
s=[]
inc=0

n, m = (int(x) for x in input().split())
for i in range(m):
    i = [int(i) for i in input().split()] 
    d.append(i)
p = [int(i) for i in input().split()]

r = 2 ** n

for i in range(r):
    x = str(bin(i).split('b')[1]).zfill(n + 1)
    s=list(x)
    s= [int(s) for s in s]
    if check(m) == 1:
            inc +=1
    
print(inc)

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

ans = 0
for i in range(2**N):
    flag = 0
    b = bin(i)[2:]
    b = '0' * (N-len(b)) + b
    for j in range(M):
        tmp = 0
        switches = S[j]
        for k, v in enumerate(switches):
            if b[v-1] == '1':
                tmp += 1
        if tmp % 2 != P[j]:
            flag = 1
            break
    if flag == 0:
        ans += 1

print(ans)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
ss = product([0, 1], repeat=n)
lb = [[0] * n for _ in range(m)]
for i in range(m):
    tmp = list(map(int, input().split()))
    k = tmp.pop(0)
    for j in tmp:
        lb[i][j-1] = 1

p = list(map(int, input().split()))
ans = 0
for state in ss:
    flag = True
    sc = 0
    for j, l in enumerate(lb):
        if sum([min(e) for e in zip(l, state)]) % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
ss = product([0, 1], repeat=n)
lb = [[0] * n for _ in range(m)]
for i in range(m):
    tmp = list(map(int, input().split()))
    k = tmp.pop(0)
    for j in tmp:
        lb[i][j-1] = 1

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

for state in ss:
    flag = True
    sc = 0
    
    for j, l in enumerate(lb):
        if sum([min(e) for e in zip(l, state)]) % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1
print(ans)

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (1 << (sw - 1)) & bits:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt_sw_on = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
                cnt_sw_on += 1
        if cnt_sw_on % 2 != lst_p[i]:
            judge = False
            break
    if judge:
        ans += 1


print(ans)

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


lst_sw = []
for _ in range(m):
    lst_sw.append(list(map(int, input().split())))
lst_p = list(map(int, input().split()))


ans = 0
for bits in range(2 ** n):
    judge = True
    for i in range(m):
        cnt = 0
        for j in range(1, len(lst_sw[i])):
            sw = lst_sw[i][j]
            if (bits >> (sw - 1)) & 1:
            
                cnt += 1
        if cnt%2 != lst_p[i]:
            judge = False
    if judge:
        ans += 1


print(ans)

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

ans = 0

s = [0] * n
for i in range(2 ** n):
    temp = i
    for j in range(n):
        s[j] = temp % 2
        temp //= 2
    for j in range(m):
        z = 0
        
        for x in range(1, k[j][0]+1):
            z += s[k[j][x] - 1]
        if p[j] != z % 2:
            break
    else:
        ans += 1

print(ans)

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


ans = 0 
for j in range(2**n): 
    cnt = 0 
    for h in range(m): 
        cnts = 0 
        for y in kls[h][1:]: 
            
            if (((j >>(y-1))) & 1): 
                
                cnts += 1
        if cnts%2 == pls[h]: 
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Solution (Python):
N, M = map(int, input().split())
ds = []
for _ in range(M):
  itr = map(int, input().split())
  k = itr.__next__()
  s = [ i-1 for i in itr]
  ds.append((k, s))

ds = [ (d[0], d[1], p) for d, p in zip(ds, map(int, input().split()))]

cnt = 0
for i in range(2**N):
  state = format(i, 'b').zfill(N)
  lights_up = True
  for k, ss, p in ds:
    s_on = 0
    for s in ss:
      if state[s] == '1':
        s_on += 1
    if s_on%2 != p:
      lights_up = False
      break
  if lights_up:
    cnt += 1

print(cnt)

Solution (Python):
def main():
    n, m = [int(i) for i in input().split()]
    s = []
    
    
    a = [0 for i in range(n)]
    for j in range(m):
        k, *switch = [int(i) for i in input().split()]
        for s in switch:
            a[s-1] |= (1 << j)
    p = int(("".join(reversed([i for i in input().split()]))), base=2)

    ans = 0
    
    for i in range(1<<n):
        t = 0
        for j in range(n):
            if (i >> j & 1) == 1:
                t ^= a[j]
        if t == p:
            ans += 1
    print(ans)

if __name__ == '__main__':
    main()

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

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

li = []
new_li = []

for i in range(2**n):
  i_bin = format(i, 'b').zfill(n)
  li.append(i_bin)
  
S = []
for i in range(m):
  s = list(map(int,input().split()))[1:]
  S.append(s)
   
p = list(map(int,input().split()))

for i in range(m):
  for j in li:
    count = 0
    for k in S[i]:
      count += int(j[k-1])
    if count % 2 == p[i]:
      new_li.append(j)
  li = new_li
  new_li = []
      
print(len(li))

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 i in range(1<<N):
  for j, k in enumerate(S):
    if sum(1 for kj in k if (i>>(kj-1) & 1))%2 != P[j]:
      break
    if j == len(S)-1:
      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)