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

Solution (Python):

 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 

N, M = [ int(x) for x in input().split() ]
KS = []
for _i in range(M):
    KS.append([ int(x) for x in input().split() ])
P = [ int(x) for x in input().split() ]

all = [[0,],[1,]]

def add_right(list):
    list0 = [ l + [0,] for l in list ]
    list1 = [ l + [1,] for l in list ]
    list0.extend(list1)
    return list0

for _i in range(N-1):
    all = add_right(all)

ans = 0
d_ans = []
for state in all:
    l_num = -1
    for ks in KS:
        l_num += 1
        switches = ks[1:]
        on = 0
        for s in switches:
            if state[s-1] == 1:
                on += 1
        if on % 2 != P[l_num]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
from itertools import product

N, M = map(int, input().split())
lights = []
for _ in range(M):
    t = list(map(int, input().split()))
    lights.append(t[1:])
cond = list(map(int, input().split()))
ans = 0
for pat in product([True, False], repeat=N):
    flag = True
    for c, l in zip(cond, lights):
        if sum([pat[idx - 1] for idx in l]) % 2 != c:
            flag = False
    if flag:
        ans += 1
print(ans)

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

last_bin = (2 ** N)
switches = [[int(i) for i in input().split()][1:] for _ in range(M)]
ps = [int(i) for i in input().split()]



counter = 0
score = 0
while last_bin != counter:
    state = '{:010b}'.format(counter)
    
    okFlag = True
    for i in range(len(switches)):
        
        states = [state[-1 * x] for x in switches[i]]
        
        if states.count('1') % 2 == ps[i]:
            pass
        else:
            okFlag = False
            break
    if okFlag:
        score += 1
    counter += 1

print(score)

Solution (Python):
n, m = (int(v) for v in input().split())
lamps = [tuple([int(e) for e in input().split()[1:]]) for _ in range(m)]
conds = [int(v) for v in input().split()]

count = 0
for state in range(2**n):
    flag = True
    for cond, lamp in zip(conds, lamps):
        mask = 0
        for sw in lamp:
            mask += 2**(sw-1)
        masked = state & mask
        bit = 0
        for _ in range(n):
            bit += masked % 2
            masked >>= 1
        if (bit + cond) % 2 != 0:
            flag = False
            break
    if flag:
        count += 1
print(count)

Solution (Python):

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()

from collections import defaultdict
light = []
for i in range(M):
    S = read_ints()
    light.append([s-1 for s in S[1:]])
P = read_ints()


n = N

ans = 0  
for i in range(1 << n):
    
    for l_idx, l in enumerate(light):
        
        ltmp = 0  
        for j in l:
            if (i >> j) % 2:
                
                ltmp += 1
        if ltmp % 2 != P[l_idx]:
            
            break
    else:
        ans += 1


print(ans)

Solution (Python):

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

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

ok_list = list(map(int, input().split()))
counter = 0
for i in range(2**n):
    tmp_counter = 0
    for light_num in range(len(switch_list)):
        light_status = ok_list[light_num]
        for switch in switch_list[light_num]:
            light_status += int(i&(1<<(switch-1))>0)
        if(light_status % 2 == 0):
            tmp_counter += 1
    if(tmp_counter == m):
        counter += 1
print(counter)

Solution (Python):
N, M = [int(_) for _ in input().split()]
KS = [[int(_) for _ in input().split()] for _ in range(M)]
P = [int(_) for _ in input().split()]
ans = 0
for s_bit in range(1 << N):
    S = []
    while s_bit:
        S += [s_bit % 2]
        s_bit //= 2
    S = [0] + S + [0] * (N - len(S))
    ok = True
    for i in range(M):
        if sum([S[_] for _ in KS[i][1:]]) % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
switch = {}
for i in range(M):
    box = list(map(int,input().split()))
    switch[i] = box[1:]
P = list(map(int,input().split()))

c = 0
for i in range(2**N):
    num = format(i, 'b')
    num = num.rjust(N, '0')
    for m_switch in range(M):
        box = 0
        for j in switch[m_switch]:
            box += int(num[j-1])
        if box%2 != P[m_switch]:
            break
        elif m_switch == M-1:
            c += 1
print(c)

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

switches = [[] for _ in range(m)]

for i in range(m):
    switches[i] = list(map(lambda x:int(x) - 1, input().split()))[1:]

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

cnt = 0

for condition in range(1 << n):
    light = True
    for i in range(m):
        oncnt = 0
        for switch in switches[i]:
            if (condition & (1 << switch)) != 0:
                oncnt += 1
        if oncnt % 2 != p[i]:
            light = False
    if light:
        cnt += 1

print(cnt)

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

k = []
s = []

for i in range(m):
    _k, *_s = map(int, input().split())
    k.append(_k)
    s.append(_s)

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

ans = 0

for i in range(2 ** n):
    bin_i = bin(i)[2:].zfill(n)
    flag = True
    for j in range(m):
        cnt = 0
        for _k in range(k[j]):
            if bin_i[s[j][_k] - 1] == "1":
                cnt += 1
        if cnt % 2 != p[j]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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

ans = 0
for i in range(2**N):
  switch = []
  for j in range(N):
    switch.append((i >> j) & 1)
  lights = 0
  for u in range(M):
    connect = 0
    for v in range(KS[u][0]):
      if switch[KS[u][v+1]-1] == True:
        connect += 1
    if connect % 2 == P[u]:
      lights += 1
  if lights == M:
    ans += 1
  
    
print(ans)

Solution (Python):
N, M = map(int, input().split())
KS = [list(map(int, input().split())) for i in range(M)]
P = list(map(int, input().split()))
ans = 0
for i in range(1<<N):
    flag = True
    for j in range(M):
        k = KS[j][0]
        s = sorted(list(map(lambda x: x-1, KS[j][1:])))
        p = P[j]
        count = 0
        comb = 0
        for si in s:
            comb = comb | (1<<si)
        res = i & comb
        for l in range(N):
            if (res>>l)&1:
                count += 1
        if (count%2 == p):
            continue
        else:
            flag = False
    if (flag):
        ans += 1


print(ans)

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

for i in range(2 ** N):
	x = bin(i)[2:].rjust(N, "0")
	flag = True
	for j in range(M):
		tmp = 0
		for k in range(1, s[j][0] + 1):
			index = s[j][k]
			if x[index - 1] == "1":
				tmp += 1
		if tmp % 2 != p[j] % 2:
			flag = False
	if flag:
		ans += 1
print(ans)

Solution (Python):
import itertools
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 si in itertools.product([0, 1], repeat=n):
    ok = True
    for mi in range(m):
        s_on = 0
        for k in range(ks[mi][0]):
            s_on += si[ks[mi][1 + k] - 1]
        if s_on % 2 != p[mi]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

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


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

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

ans = 0
for i in range(2 ** N):
    tmp = []
    den_count = 0
    for j in reversed(range(N)):
        if (i & (1 << j)):
            
            tmp.append(1)
        else:
            
            tmp.append(0)
    for k in range(len(den)):
        
        switch_count = 0
        for z in den[k]:
            if tmp[z-1] == 1:
                switch_count += 1
        if switch_count % 2 == p[k]:
            den_count += 1
        else:
            break
    if den_count == M:
        ans += 1
print(ans)

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

li = []
ans = 0

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

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

switch = []

def onoff(count):
    global ans
    if count == n:
        for i in range(m):
            sum = 0
            for j in li[i]:
                sum += switch[j-1]
            if sum % 2 != lip[i]:
                break
            if i == m-1:
                ans += 1
    else:
        switch.append(0)
        onoff(count+1)
        switch.pop(-1)
        switch.append(1)
        onoff(count+1)
        switch.pop(-1)

onoff(0)

print(ans)

Solution (Python):
N,M = map(int,input().split())
s_info = [[] for j in range(M)]
for i in range(M):
	l = list(map(int,input().split()))
	n_l = [x-1 for x in l]
	s_info[i] = n_l[1:]
cond = list(map(int,input().split()))


def dec2bin(n, d):
	ret = []
	for i in range(d):
		ret.append(n%2)
		n = n // 2
	return ret

ans = 0
for i in range(2**N):
	switch = dec2bin(i, N)
	flg = True
	for m in range(M):
		if sum([1 for n in range(N) if switch[n] == 1 and n in s_info[m]]) % 2 != cond[m]:
			flg = False

		
	if flg:
		ans += 1

print(ans)

Solution (Python):
def solve():
    n, m = map(int, input().split())
    M = [0] * m
    for i in range(m):
        _, *S = map(int, input().split())
        for s in S:
            M[i] |= (1 << (s - 1))
    P = list(map(int, input().split()))
    ans = 0
    for i in range(1 << n):
        for j in range(m):
            if bin(i & M[j])[2:].count('1') % 2 != P[j]:
                break
        else:
            ans += 1
    print(ans)
solve()

Solution (Python):
import itertools
n, m = map(int, input().split())
data = []
for i in range(m):
    tmp = list(map(int, input().split()))
    data.append([i, tmp[0], tmp[1:]])
ps = list(map(int, input().split()))
situ = list(itertools.product("01", repeat=n))
ans = 0
for one in situ:
    tmp1 = 0
    
    for light in data:
        tmp2 = 0
        
        for index in light[2]:
            if one[index - 1] == "1":
                tmp2 += 1
        if tmp2 % 2 == ps[light[0]]:
            tmp1 += 1
    if tmp1 == m:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int, input().split())
K = []
S = []
for i in range(M):
    k,*s = map(int, input().split())
    K.append(k)
    tmp = 0
    for j in s:
        tmp += 1<<(j-1)
    S.append(tmp)
P = list(map(int, input().split()))

result = 0
for i in range(1<<(N)):
    cnt = 0
    
    for j in range(M):
        tmp = S[j] & i
        val = str(bin(tmp)).count('1')
        
        if val % 2 == P[j]:
            cnt += 1
    
    if cnt == M:
        result += 1

print(result)

Solution (Python):
def all_lightsup(A, switches, k, p):
    for i in range(M):
        light = 0
        elements = k[i]
        for j in range(elements):
            if A[switches[i][j]-1] == 1:
                light += 1
        if light % 2 != p[i]:
            return False
    return True

N, M = map(int,input().split())
switches = []
k = []
ans = 0
for i in range(M):
    temp = list(map(int,input().split()))
    k.append(temp[0])
    switches.append(temp[1:])
p = list(map(int,input().split()))

num_of_state = 2**N
for i in range(num_of_state):
    val = i
    temp = []
    for j in range(N):
        temp.append(val%2)
        val //= 2
    if all_lightsup(temp, switches, k, p):
        ans += 1
print(str(ans))

Solution (Python):
n,m=[int(x) for x in input().split()]
k,s=[],[]
for _ in [0]*m:
    val=[int(x) for x in input().split()]
    k.append(val[0])
    s.append(val[1:])
p=[int(x) for x in input().split()]
ans=0
for i in range(1<<n):
    for j in range(m):
        on_switch_num=0
        for l in range(n):
            if l+1 in s[j] and (i>>l & 1) == 1:
                on_switch_num+=1
        if on_switch_num%2==p[j]:
            continue
        else:
            break
    else:
        ans+=1
print(ans)

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

  K = [0] * M
  for i in range(M):
    s = [int(i) for i in input().split()]
    s.pop(0)
    v = 0
    for j in s: v += 2 ** (j - 1)
    K[i] = v

  P = [int(i) for i in input().split()]

  def check(v):
    for i in range(M):
      f = v & K[i]
      count = bin(f).count('1')
      if P[i] != (count % 2): return False
    return True

  ans = 0
  for i in range(2 ** N):
    if check(i): ans += 1

  return ans

print(solve())

Solution (Python):
from itertools import product
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    tmp1 = list(map(int, input().split()))
    K.append(tmp1[0])
    tmp2 = []
    for j in tmp1[1:]:
        tmp2.append(j-1)
    S.append(tmp2)

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

ans = 0
for v in product([0, 1], repeat=N):
    flag = False
    cnt_M = 0
    for j in range(M):
        cnt_light = 0
        for i in range(N):
            for k in range(K[j]):
                if v[i] == 1 and i == S[j][k]:
                    cnt_light += 1
        if cnt_light % 2 == P[j]:
            cnt_M += 1
        else:
            break
        if cnt_M == M:
            ans += 1
print(ans)

Solution (Python):
def IntToState(X, N):
    ret = []
    bina = bin(X)
    for i in range(2, len(bina)):
        ret.append(int(bina[i]))
    while len(ret) <= N:
        ret.insert(0,0)
    return ret

def solve():
    N, M = [int(_) for _ in raw_input().split()]
    SK = []
    for i in range(M):
        SKi = [int(_) for _ in raw_input().split()]
        SK.append(SKi)
    p = [int(_) for _ in raw_input().split()]
    ans = 0
    MAX_CASE = 1<<N
    for i in range (MAX_CASE):
        state = IntToState(i, N)
        satisfi = True
        for j in range(M):
            tmp_sum = 0
            for k in range(1, SK[j][0] + 1):
                tmp_sum += state[SK[j][k]]
            if tmp_sum % 2 != p[j]:
                satisfi = False
                break
        if satisfi:
            ans += 1
    print ans

if __name__ == '__main__':
    solve()

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op



inf = float('inf')
N = 0


def set_inputs():
    global N
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    
    n, m = get_li()
    K2S = defaultdict(set)
    S2K = defaultdict(set)
    for i in range(m):
        ks = get_li()
        S = ks[1:]
        for s in S:
            K2S[i+1].add(s)
            S2K[s].add(i+1)
    P = get_li()
    ans = 0
    for x in its.product([0, 1], repeat=n):
        valid = True
        for i in range(m):
            on = 0
            for j in K2S[i+1]:
                on += x[j-1]
            if on % 2 != P[i]:
                valid = False
                break
        if valid:
            ans += 1
    print(ans)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Solution (Python):
list=input().split(" ")
n=int(list[0])
m=int(list[1])

denkyu=[]

for i in range(m):
    info=input().split(" ")
    for j in range(len(info)):
        info[j]=int(info[j])
    list=[]
    for i in range(n):
        list.append(0)
    
    
    for j in range(len(info)-1):
        list[info[j+1]-1]=1
    denkyu.append(list)



shogo=[]

for x in range(2**n):
    shinsu=[]
    for y in range(n):
        if x%2==1:
            shinsu.append(1)
            x=int((x-1)/2)
        else:
            shinsu.append(0)
            x=int((x)/2)
    shogo.append(shinsu)



plist=input().split(" ")
for j in range(len(plist)):
    plist[j]=int(plist[j])




kosu=0
for s in shogo:
    switch=1
    now=0
    complete=0
    while switch==1:
        match=0
        for i in range(n):
            if s[i]==denkyu[now][i] and s[i]==1:
                
                match+=1
        if match%2==plist[now]:
            now+=1
        else:
            switch=0
        if now==(m):
            if switch==1:
                complete=1
                switch=0
                
    if complete==1:
        kosu+=1
        
print(kosu)

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

KS = []
for _ in range(M):
    ks = list(map(int, input().split()))
    KS.append(ks)
    
P = list(map(int, input().split()))
def checker(on_off):
    for i, ks, in enumerate(KS):
        sum_s = sum([ on_off[s-1] for s in  ks[1:]])
        if sum_s % 2 != P[i]:
            return 0
    return 1
        

def dfs(i, on_off):
    if i == 0:
        
        return checker(on_off)
    
    a = dfs(i-1, on_off[:] + [0])
    b = dfs(i-1, on_off[:] + [1])
    return a + b
        
    
ans = dfs(K, [])
print(ans)

Solution (Python):
from itertools import product

n, m = map(int, input().split())
ans = 0
S = [list(map(int, input().split())) for i in range(m)]
P = list(map(int, input().split()))
for combi in product([True, False], repeat=n):
    result = True
    for i in range(len(S)):
        p = sum([int(combi[s - 1]) for s in S[i][1:]])
        if p % 2 != P[i]:
            result = False
            break
    if result:
        ans += 1
print(ans)

Solution (Python):
n,m = map(int,input().split())
lis = []
for i in range(m):
  l = list(map(int,input().split()))
  l.remove(l[0])
  lis.append(l)
ch = list(map(int,input().split()))
ans = 0
for i in range(2 ** n):
  key = 1
  s = str(format(i,"b").zfill(n))
  for j in range(m):
    num = 0
    for nu in lis[j]:
      if s[nu-1] == "1":
        num += 1
    if num % 2 != ch[j]:
      key = 0
  if key == 1:
    ans += 1

print(ans)

Solution (Python):
import itertools as it
import sys
sys.setrecursionlimit(10**9)
"""
N=int(input())
D=[]
for i in range(N):
  s,p=input().split()
  D.append((s, int(p), i+1))
D.sort(key=lambda d: (d[0], -d[1], d[2]))

for d in D:
  print(d[2])
"""
N,M=map(int, input().split())
K=[]
S=[]
for i in range(M):
  k,*si=map(int, input().split())
  K.append(k)
  S.append(list(sorted(si)))
P=list(map(int, input().split()))

L=it.product([0,1], repeat=N)
cnt=0

for l in L:
  ok=True
  for i,si in enumerate(S):
    pi=P[i]
    sumS=len(list(filter(lambda it: l[it-1]==1, si)))
    
    if sumS%2 != pi: ok=False
  if ok: cnt += 1
print(cnt)

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

switch,denkyu=map(int,input().split())
connect=[]
for i in range(denkyu):
  l=list(map(int,input().split()))
  connect.append(l)
amari=list(map(int,input().split()))
okcombcounter=0
for i in range(2**switch):
  state=format(i,'b').zfill(switch)
  tentoucounter=0
  for j in range(denkyu):
    oncounter=0
    for k in range(connect[j][0]):
      if state[connect[j][k+1]-1]=='1':
        oncounter+=1
    if oncounter%2==amari[j]:
      tentoucounter+=1
  if tentoucounter==denkyu:
    okcombcounter+=1
print(okcombcounter)

Solution (Python):
from itertools import product
N,M = map(int,input().split())
K = []
S = []
for i in range(M):
    k, *s = map(int,input().split())
    K.append(k)
    S.append(s)
P = list(map(int,input().split()))

pro = product([0,1],repeat=N)
ans = 0
for pr in pro:

    flag = True
    for i in range(M):
        tmp = 0
        for p in S[i]:
            tmp += pr[p-1]
        if tmp % 2 != P[i]:
            flag = False
            break
    if flag: ans += 1
print(ans)

Solution (Python):
N,M=[int(x) for x in input().split()]
SSS=[]
for _ in range(M):
    SSS.append([int(x) for x in input().split()][1:])
    
ps=[int(x) for x in input().split()]

def dfs(L,num):
    if len(L)==N:
        bol=True
        for m,SS in enumerate(SSS):
            r=0
            for s in SS: 
                r+=L[s-1]
            if r%2!=ps[m]:
                bol=False
                break
        if bol:
            return num+1
        else:
            return num
    else:
        num=dfs(L+[1],num)
        num=dfs(L+[0],num)
        return num

result=0
result=dfs([1],result)
result=dfs([0],result)
print(result)

Solution (Python):
from itertools import product

n, m = list(map(int, input().split()))
s = []
for _ in range(m):
    _, *si = list(map(int, input().split()))
    s.append(si)
p = list(map(int, input().split()))

ans = 0
for l in product([False, True], repeat=n):
    sat = 0
    for si, pi in zip(s, p):
        cnt = 0
        for ssi in si:
            if l[ssi - 1]:
                cnt += 1

        if cnt % 2 != pi:
            break
        else:
            sat += 1
    if sat == m:
        ans += 1

print(ans)

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

ls = []
st = { i+1 for i in range(N) }
for i in range(M):
    inl = list(map(int, input().split()))
    switches = inl[1:]
    ls.append(switches)

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

res = [0]
def check(inpu = st, mp = {}, res_ = res):
    if len(inpu):
        val = inpu.pop()
        mp0 = mp.copy()
        mp0[val] = 0
        mp1 = mp.copy()
        mp1[val] = 1
        check(inpu.copy(), mp0)
        check(inpu.copy(), mp1)
    else:
        
        all_ = True
        for key, sws in enumerate(ls):
            summed = 0
            for sw in sws:
                summed += mp[sw]
            summed %= 2
            if summed != checker[key]:
                all_ = False
        if all_:
            res[0] += 1

check()
print(res[0])

Solution (Python):
n, m = map(int, input().split())
switch = [[] for i in range(n)]
for j in range(m):
    a = [(int(i) - 1) for i in input().split()]
    for aa in a[1:]:
        switch[aa].append(j)
p = [int(i) for i in input().split()]
ans = 0
for i in range(2 ** n):
    calc = [0 for _ in range(m)]
    k = bin(i)[2:]
    k = (n - len(k)) * ["0"] + list(k)
    for j, kk in enumerate(k):
        if kk == "1":
            for s in switch[j]:
                if calc[s] == 0:
                    calc[s] = 1
                else:                    
                    calc[s] = 0
    if calc == p:
        ans += 1
print(ans)

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

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

def check(number,s_list,p):
    string = list(map(int,reversed("{:010b}".format(number))))
    cnt = 0
    for s in s_list:
        if string[s-1] == 1:
            cnt += 1
    if cnt % 2 == p:
        return True
    else:
        return False

cnt= 0
for i in range(2**N):
  if   all([check(i, s_lists[j],P[j]) for j in range(M)]):
    cnt += 1
print(cnt)

Solution (Python):
import itertools
n,m=map(int,input().split())
sw_list=[]
for i in range(m):
    num,*sw=map(int,input().split())
    sw_list.append(sw)
p_list=[int(i) for i in input().split()]

count=0

for pat in itertools.product(range(2), repeat=n):
    blnOK=True
    for i in range(m):
        sump=0
        for sw in sw_list[i]:
            if pat[sw-1]==1:
                sump+=1
        if sump%2!=p_list[i]:
            blnOK=False
    if blnOK:
        count+=1  

print(count)

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

res = 0
for i in range(2**n):
    x = bin(i)[2:][-n:].zfill(n)
    if all([sum([int(x[ii-1]) for ii in l[i]]) % 2 == p[i] for i in range(len(l))]):
        res += 1
print(res)

Solution (Python):
N,M = map(int,input().split())
swi = [[]for i in range(N)]
for i in range(M):
    tmp = list(map(int,input().split()))
    for j in tmp[1:]:
        swi[j-1].append(i)
p = list(map(int,input().split()))
ans = 0
for i in range(2**N,2**(N+1)):
    ramp = [0]*M
    i = bin(i)
    for j in range(N):
        if i[j+3] == "1":
            for k in swi[j]:
                ramp[k] += 1
    for i in range(M):
        ramp[i] = ramp[i]%2
    if ramp == p:
        ans += 1
print(ans)

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

ks = []
sss = []
for _ in range(M):
  inp = [int(i) for i in input().split()]
  ks.append(inp[0])
  sss.append(inp[1:])
  
ps = [int(i) for i in input().split()]

count = 0
for i in range(2**N):
  pattern = [(i >> j) & 1 for j in range(N)]
  ok = True
  for m in range(M):
    p = ps[m]
    ss = sss[m]
    
    if sum([int(pattern[s-1]) for s in ss]) % 2 == p:
      ok = True
    else:
      ok = False
      break
  if ok:
    count += 1
    
print(count)

Solution (Python):
n, m = map(int, input().split())
k = []
for i in range(m):
    k.append(list(map(int, input().split())))
p = list(map(int, input().split()))
count = 0
for i in range(2**n):
    flag = True
    for q_idx, query in enumerate(k):
        count_p = 0
        for q in query[1:]:
            if (i & 2**(q-1)) > 0:
                count_p += 1
        if count_p % 2 != p[q_idx]:
            flag = False
    if flag:
        count += 1
print(count)

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

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

print(ans)

Solution (Python):
def dfs(N, M, Bulb, P, switches, cur):
  if cur == N:
    for i, b in enumerate(Bulb):
      s = 0
      for x in b[1:]:
        s += switches[x-1]
      if s % 2 != P[i]:
        return 0
    return 1
  else:
    a = 0
    switches[cur] = 0
    a += dfs(N, M, Bulb, P, switches, cur+1)
    switches[cur] = 1
    a += dfs(N, M, Bulb, P, switches, cur+1)
    return a

N, M = map(int, input().split())
Bulb = [list(map(int, input().split())) for _ in range(M)]
P = list(map(int, input().split()))
print(dfs(N, M, Bulb, P, [0] * N, 0))

Solution (Python):
l = raw_input().split()
N = int(l[0])
M = int(l[1])

K = []
S = []
P = []

for i in range(M):
    l = raw_input().split()
    t = [int(x) for x in l]
    K.append(t[0])
    S.append(t[1:])

l = raw_input().split()
P = [int(x) for x in l]



def numBits(n):
    count = 0
    while n > 0:
        if n % 2 == 1:
            count += 1
        n /= 2
    return count

def solve(n, S, p):
    
    count = 0
    for s in S:
        
        count += (n >> (s - 1)) & 1
    
    return p == (count  & 1)

ans = 0
for j in range(2**N):
    
    ret = True
    for i in range(len(S)):
        s = S[i]
        p = P[i]
        
        if not solve(j, s, p):
            ret = False
            break
    if ret:
        ans += 1
print(ans)

Solution (Python):
from copy import deepcopy

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

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

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

def dfs(sw, depth):
    if depth == N:
        for i in range(M):
            counter = 0
            for j in s[i]:
                if sw[j-1] == 1:
                    counter += 1
            if counter % 2 != p[i]:
                return 0
        return 1
    
    ans = 0
    copy1 = deepcopy(sw)
    copy2 = deepcopy(sw)
    copy1.append(0)
    copy2.append(1)
    ans += dfs(copy1, depth + 1)
    ans += dfs(copy2, depth + 1)
    return ans

print(dfs([], 0))

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop, heapify, heapreplace

class Solution:
    def main(self):
        N, M = map(int, input().split())
        K = []
        S = []
        for i in range(M):
            line = list(map(int, input().split()))
            k = line[0]
            s = line[1:]
            K.append(k)
            S.append(s)
        P = list(map(int, input().split()))
        on = [0] * N
        
        
        res = 0
        for _ in range(2**N):
            
            for i in range(M):
                if sum([on[idx-1] for idx in S[i]]) % 2 != P[i]:
                    break
            else:
                res += 1
            self.increment(on, 0)
        print(res)

    def increment(self, array, i):
        if len(array) <= i:
            return array
        elif array[i] == 0:
            array[i] = 1
            return array
        else:
            array[i] = 0
            return self.increment(array, i+1)


if __name__ == '__main__':
    Solution().main()