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 sys
input = sys.stdin.readline

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		st = set()
		for i in range(n):
			if l[i] == 1:
				st.add(i + 1)
		for k, sw in enumerate(v):
			
			if len(sw.intersection(st)) % 2 != p[k]:
				return
		
		count += 1
		
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		for k, sw in enumerate(v):
			st = set()
			for i in range(n):
				if l[i] == 1:
					st.add(i + 1)
			
			if len(sw.intersection(st)) % 2 != p[k]:
				return
		
		count += 1
		
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

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 mask in range(0,1<<N):
    flag = True
    for i, line in enumerate(S):
        cnt = 0
        for s in line:
            if ((mask >> (s-1) & 1)):
                cnt += 1
        if cnt % 2 != P[i]:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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

v = []
p = []
count = 0
m = 0
def rec(l, n):
	global count
	if len(l) == n:
		c = 0
		for k, sw in enumerate(v):
			st = set()
			for i in range(n):
				if l[i] == 1:
					st.add(i + 1)
			
			if len(sw.intersection(st)) % 2 == p[k]:
				c += 1
		
		if c == m:
			count += 1
		
		return
	l.append(0)
	rec(list(l), n)
	l.pop()
	l.append(1)
	rec(list(l), n)

def main():
	global v
	global p
	global m
	n, m = map(int, input().strip().split())
	for i in range(m):
		tmp = list(map(int, input().strip().split()))
		v.append(set(tmp[1:]))
	p = list(map(int, input().strip().split()))
	rec([], n)
	print(count)

if __name__ == '__main__':
	main()

Solution (Python):
def can(state, m, bulb, p):
	"""For given switch state, determine all bulbs are turned on."""
	for i in range(m):
		cnt = 0 
		for j in bulb[i]:
			if (state & (1<<(j-1))):
				cnt += 1
		if cnt % 2 != p[i]:
			return False
	return True

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

ans = 0
for i in range(1<<n):
	if can(i, m, bulb, p):
		ans += 1
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def create_bin_string(data, num):
    c_bin = "{:b}".format(data)
    switches = c_bin
    for _ in range(0, num-len(c_bin)):
        switches = "0" + switches
    return switches


def solve(N, M, data, Ps):
    lamp_sw_comb = list(map(lambda x: string_to_int(x), data))
    lamp_sw_p = string_to_int(Ps)

    count = 0
    for c in range(0, 2**N):
        switches = create_bin_string(c, N)

        are_all_light = True
        for i, lamp_sw in enumerate(lamp_sw_comb):
            on_num = 0
            for j, sw in enumerate(lamp_sw):
                if j == 0:
                    continue
                if switches[sw-1] == "1":
                    on_num += 1
            if on_num % 2 != lamp_sw_p[i]:
                are_all_light = False
                break

        if are_all_light:
            count += 1
    return count


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    data = inputs(M)
    Ps = input()
    ret = solve(N, M, data, Ps)
    print(ret)

Solution (Python):
import sys
import numpy as np

input = sys.stdin.readline
N, M = map(int, input().split())
ss = [None] * M
for i in range(M):
    in_ = list(map(int, input().split()))
    ss[i] = [s-1 for s in in_[1:]]
ps = list(map(int, input().split()))

ans = 0
switch = [0] * N
for x in range(2**N):
    incl = 1
    bin_x = format(x, '0{}b'.format(N))
    switch = np.array([int(bin_x[i]) for i in range(N)])
    for i in range(M):
        if switch[ss[i]].sum() % 2 != ps[i]:
            incl = 0
            break
    ans += incl
        
print(ans)

Solution (Python):
import sys
from collections import deque  
from collections import defaultdict  
from heapq import heapify, heappush, heappop, heappushpop  
from bisect import bisect_left, bisect_right  



s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2sss = lambda n: [list(sys.stdin.readline().rstrip()) for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7


def getBitsL(n, L):
    bits = [0] * L
    for i in range(L):
        bits[i] = (n & 1) == 1
        n >>= 1
    return bits

def main():
    N, M = i2nn()
    KS = ii2nnn(M)
    P = i2nn()
    n = 0
    for i in range(2**N):
        bits = getBitsL(i, N)
        b = True
        for j, ks in enumerate(KS):
            t = 0
            for k in ks[1:]:
                if bits[k-1]:
                    t += 1
            if t % 2 != P[j]:
                b = False
        if b:
            n += 1
    print(n)

main()

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

Solution (Python):
N, M = map(int, input().split())
ss = []
for i in range(M):
  ws = [int(w) for w in input().split()]
  ws.pop(0)
  s = 0
  for w in ws:
    s |= 1 << (w-1)
  ss.append(s)

ps = [int(w) for w in input().split()]

def countbit(o):
  c = 0
  for n in range(N):
    if o & (1 << n) != 0:
      c += 1
  return c
r = 0
for i in range(1 << N):
  ok = True
  for m in range(M):
    s, p = ss[m], ps[m]
    o = i & s
    c = countbit(o)
    
    if c % 2 != p:
      ok = False
      break
  if ok:
    r += 1
print(r)

Solution (Python):
n,m=map(int,input().split())
s=[]
for _ in range(m):
  a=list(map(int,input().split()))
  s.append(a)
p=list(map(int,input().split()))
i_b=[]
for i in range(2**n):
  i_b.append(str(bin(i))[2:].zfill(n))
ans=0
for i in i_b:
  i_a=[]
  for j in range(m):
    j_s=0
    for k in range(1,s[j][0]+1):
      j_s+=int(i[s[j][k]-1])
    i_a.append(j_s%2)
  if i_a==p:
    ans+=1
print(ans)

Solution (Python):


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

k = []
s = []
for _ 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 bits in range(2**n):
    flag = True
    for i in range(m):
        on_sum = 0
        for switch in s[i]:
            on_sum += ((bits >> (switch - 1)) & 1)
        flag = flag and ((on_sum % 2) == p[i])
    if flag:
        ans += 1
print(ans)

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(2 ** n):
    for mi in range(m):
        on_count = 0
        for ni in range(n):
            if (i & (1 << ni)) and (ni + 1 in s[mi]):
                on_count += 1
        if on_count % 2 != p[mi]:
            break
    else:
        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()))

def check(ar):
    cnt = 0
    for j in range(M):
        count = 0
        for k in ks[j][1::]:
            if ar[k-1] == 1:
                count += 1
        if count%2 == p[j]:
            cnt += 1
    return (cnt == M)


def dfs(n, ar):
    if n == 0:
        if check(ar):
            return 1
        else:
            return 0
    else:
        return dfs(n-1, ar+[0]) + dfs(n-1, ar+[1])
arr = []
ans = dfs(N, arr)
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):
    cnt = 0
    for j in range(M):
        count = 0
        for k in ks[j][1::]:
            if (i >> k-1)&1 == 1:
                count += 1
        if count%2 == p[j]:
            cnt += 1
    if cnt == M:
        ans += 1
print(ans)

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

count = 0
for i in range(2**n):
    on = 0
    for j in range(m):
        cnt = 0
        for s in ks_list[j][1:]:
            if (i >> s-1)&1 == 1:
                cnt += 1
        if cnt%2 == p_list[j]:
            on += 1
    if on == m:
        count += 1
print(count)

Solution (Python):

import itertools
L = [0,1]
count = 0

N,M = map(int,input().split())
k = []
s = []

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

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

bit_list = list(itertools.product([0,1],repeat = N))

for i in bit_list:
    
    for j in range(M):
        
        counter = 0
        tmp = list(s[j])
        
        for l in tmp:
            if i[l-1] == 1:
                counter += 1
        
        if counter % 2 != p[j]:
            break
        
        if j == M-1:
            count += 1

print(count)

Solution (Python):
N, M = map(int, input().split())
Light = []
for _ in range(M):
    Tmp = list(map(int, input().split()))
    Tmp.pop(0)
    Light.append(set(Tmp))
P = list(map(int, input().split()))

import itertools
bit = list(itertools.product(['On', 'Off'], repeat=N))
ans = [0 for _ in range(2**N)]

for idx in range(M):
    light = Light[idx]
    p = P[idx]
    for j, switchs in enumerate(bit):
        cnt = 0
        for l in light:
            if switchs[l-1] == 'On':
                cnt += 1
        if cnt % 2 == p:
            ans[j] += 1
print(ans.count(M))

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

list_k = list()
list_p = list()

for i in range(m):
    list_k.append(list(map(int, input().split())))

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

answer = 0

for i in range(2 ** n):
    

    switch = format(i, 'b').zfill(n)[::-1]

    for idx, p in enumerate(list_p):
        check_k = list_k[idx][1:]

        target_switch = [switch[k - 1] for k in check_k]

        if target_switch.count('1') % 2 != p:
            break
    else:
        answer += 1

print(answer)

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

A = [[0] * N for i in range(M)]

for i in range(M):
  L = list(map(int, input().split()))
  for a in L[1:]:
    A[i][a-1] = 1
    
P = list(map(int, input().split())) 

ans = 0
for X in list(product([0,1], repeat=N)):
  flg = True
  for i in range(M):
    work = 0
    for j in range(N):
      work += A[i][j] * X[j]
      
    if work % 2 == P[i]:
      continue
    else:
      flg = False
      break
  if flg:
    ans += 1
    
print(ans)

Solution (Python):
from itertools import product
n, m = map(int, input().split())
s = []
for _ in range(m):
    _, *t = map(int, input().split())
    s.append(t)
p = [int(i) for i in input().split()]

cnt = 0
for fl in product([0, 1], repeat=n):
    for i in range(m):
        if sum(fl[tmp - 1] for tmp in s[i]) % 2 != p[i]:
            break
    else:
        cnt += 1

print(cnt)

Solution (Python):
swithCount, lightCount = map(int, input().split())
swithList = [0] * swithCount

for lightIndex in range(lightCount):
    connectedSwitchList = list(map(int, input().split()))
    for si in connectedSwitchList[1:]:
        switchIndex =  si - 1
        swithList[switchIndex] = swithList[switchIndex] | 1 << lightIndex

expectedLightStatusList = list(map(int, input().split()))
expectedLightStatus = 0

for i, eachStatus in enumerate(expectedLightStatusList):
    expectedLightStatus = expectedLightStatus | eachStatus << i

resultCount = 0
for eachSwitchSet in range(1 << swithCount):
    actuallyLightStatus = 0
    for switchIndex in range(swithCount):
        if eachSwitchSet >> switchIndex & 1:
            actuallyLightStatus = actuallyLightStatus ^ swithList[switchIndex]

    if expectedLightStatus == actuallyLightStatus:
        resultCount += 1

print(resultCount)

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

cnt = 0
for i in range(2**n):
    bi = format(i, "010b")[::-1]
    flag = True
    for j in range(len(sl)):
        c = 0
        for idx in sl[j]:
            c += int(bi[int(idx)-1])
        if c % 2 != p[j]:
            flag = False
            break
    if flag:
        cnt += 1
print(cnt)

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

ans = 0
for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if ((i >> j) & 1 ):
            switch[j] += 1
    on = 0
    for k in range(M):
        count = 0
        for l in range(1,s[k][0]+1):
            if switch[s[k][l]-1] == 1:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == M:
        ans += 1
    
print(ans)

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

ks_lists = [list(map(int, input().split())) for _ in range(M)]
p_list = list(map(int, input().split()))


n_combi = 0
for combi in range(1 << N):
    Flag = True
    for i in range(M):
        k = ks_lists[i][0]
        s_list = ks_lists[i][1:]
        p = p_list[i]

        tmp_sum = 0
        for s in s_list:
            tmp_sum += (combi >> (s-1)) & 1
        if tmp_sum % 2 != p:
            Flag = False
            break
    if Flag:
        n_combi += 1

print(n_combi)

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

conditions = list(map(int,input().split(" ")))

p_num = 2**n
count = 0
for i in range(p_num):
  on_switch = []
  flag = True
  for digit in range(n):
    if (i%2 == 0):
      on_switch.append(digit+1)
    i = i//2
  for j in range(m):
    buf = [x for x in on_switch if x in lights[j]]
    if len(buf) % 2 != conditions[j]:
      flag = False
  if flag:
    count += 1

print(count)

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

ans = 0

def tekito(swit):
    for i in range(m):
        judge_kun = 0
        for s in ks[i][1:]:
            judge_kun += swit[s-1]
        if judge_kun % 2 == (1-p[i]):
            return False
    return True

import itertools
for swit in itertools.product([0, 1], repeat=n):
    if tekito(swit):
        ans+=1


print(ans)

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

count = 0

for i in range(2 ** n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n)
    for j in ks:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k) - 1])
        if swith_sum % 2 == p[ks.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:
        count += 1

print(count)

Solution (Python):
from copy import deepcopy
n, m = map(int, raw_input().split())
S = []
for _ in range(m):
    line = map(int, raw_input().split())
    S.append(line[1:])
P = map(int, raw_input().split())
perms = [[0] * n]
for i in range(n):
    for j in range(len(perms)):
        p2 = deepcopy(perms[j])
        p2[i] = 1
        perms.append(p2)
ways = 0
for perm in perms:
    satisfy = True
    for k in range(m):
        count = 0
        for s in S[k]:
            if perm[s-1] == 1:
                count += 1
        if count % 2 != P[k]:
            satisfy = False
            break
    if satisfy:
        ways += 1
print ways

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

count= 0

for i in range(2**n):
    swith = str(bin(i))[2:]
    swith_num = swith.zfill(n) 
    for j in info_list:
        flag = 0
        swith_sum = 0
        for k in j[1:]:
            swith_sum += int(swith_num[int(k)-1])
        if swith_sum%2 == p_list[info_list.index(j)]:
            pass
        else:
            flag = 1
            break
    if flag == 0:        
        count += 1

print(count)

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

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

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

ans = 0
for i in range(2**N): 
  for j in range(M): 
    cnt = 0 
    for k in ls[j]:
      if i&(1<<(k-1)): 
        cnt += 1
    if cnt%2 != p[j]:
      break
  else:
    ans +=1
print(ans)

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

A=[]
total=0
count=0
flag=0
for j in range(M+1):
    A.append(list(map(int, input().split())))

for i in range(2**N):
    switch=format(i,'b')
    switch=switch[::-1]+'0000000000'
    

    for a in range(M):
        for b in range(1,len(A[a])):
            
            count += int(switch[int(A[a][b])-1])
            

        if count%2!=A[M][a]:
            flag=1
        count = 0
    if flag==0:
        total +=1
    flag=0
    count=0
print(total)

Solution (Python):
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

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

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            break
    else:
        count += 1
    state = [0 for i in range(M)]
print(count)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
D = [0]*M
for i in range(M):
    temp = list(map(int, input().split()))
    for j in temp[1:]:
        D[i] +=  2**(j-1)
p = list(map(int, input().split()))
ans = 0
for s in range(2**N):
    temp = True
    for i,d in enumerate(D):
        temp &= bin(s&d).count('1')%2==p[i]
    if temp:
        ans += 1
print(ans)

Solution (Python):










import math
import sys


N, M=map(int, sys.stdin.readline().split())




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

for bulb_idx in range(M):
    switches = list(map(int, sys.stdin.readline().split()))
    bulb_bit = 1 << bulb_idx 

    
    for sw in switches[1::]:
        sw_idx = (sw - 1) 
        bulb_list[sw_idx] = bulb_list[sw_idx] | bulb_bit

bulb_conds = list(map(int, sys.stdin.readline().split()))

bulb_cond = 0
for i, bc in enumerate(bulb_conds):
    bulb_cond |= bc << i

light_num = 0



for bit_ptn in range(1 << N):
    t = 0 
    for i in range(N):
        if bit_ptn >> i & 1:
            t = t ^ bulb_list[i]
    if t == bulb_cond:
        light_num += 1

print(light_num)

Solution (Python):
N,M = map(int, input().split())
connect = [[0,0,0]]
on_off = [0]*(N+1)
result = 0
for _ in range(M):
    k = list(map(int, input().split()))
    connect.append(k[1:])
p = list(map(int, input().split()))

for cnt in range(0,2**N):
    bin_str = list(format(cnt, 'b'))
    i = len(on_off)-len(bin_str)
    for num in bin_str:
        on_off[i] = int(num)
        i += 1
    for i in range(1,M+1):
        total = 0
        for j in connect[i]:
            total += on_off[j]
        if total % 2 != p[i-1]:
            break
        elif i == M:
            result += 1
print(result)

Solution (Python):

import bisect
from collections import defaultdict

def main():
    N, M = map(int, input().split())
    switches = defaultdict(list)
    for i in range(M):
        ks = list(map(int, input().split()))
        for s in ks[1:]:
            switches[s].append(i)
    p_list = list(map(int, input().split()))

    cnt = 0
    for i in range(2 ** N):
        on_nums = defaultdict(int)
        bits = bin(i)[2::][::-1]
        for k, b in enumerate(bits):
            if b == '1':
                for s in switches[k+1]:
                    on_nums[s] += 1

        if all([on_nums[s] % 2 == p_list[s] for s in range(M)]):
            cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        a = list(map(int, input().split()))
        S.append([b-1 for b in a[1:]])
    P = list(map(int, input().split()))

    
    mask = [0 for _ in range(M)]
    for i in range(M):
        m = 0
        for s in S[i]:
            m += 2 ** s
        mask[i] = m
    
    ans = 0
    for k in range(2 ** N):
        res = True
        for i in range(M):
            if bin(k & mask[i]).count('1') % 2 != P[i]:
                res = False
                break
        if res:
            ans += 1

    print(ans)

main()

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

bit_li = []
for i in range(2**n):
    bit = [0] * n
    for j in range(n):
        if (i >> j) & 1:
            bit[j] = 1
    bit_li.append(bit)

count = 0
for i in range(2 ** n):
    flag = 0
    for j in range(m):
        elem_sum = 0
        for l in range(k[j]):
            elem_sum += bit_li[i][s_li[j][l] - 1]
        if elem_sum % 2 == p[j]:
            flag += 1
    if flag == m:
        count += 1

print(count)

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



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


def main():
    N, M = map(int, input().split())
    state = []
    for _ in range(M):
        S = list(map(int, input().split()))

        v = [0] * N
        for s in S[1:]:
            v[s - 1] = 1
        state.append(v)
    P = list(map(int, input().split()))

    ans = 0
    for pattern in product([0, 1], repeat=N):
        all_on = True
        for i in range(M):
            num_on = 0
            for j in range(N):
                if state[i][j] == 1 and pattern[j] == 1:
                    num_on += 1

            if num_on % 2 != P[i]:
                all_on = False
                break

        ans += all_on

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):



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

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




ans = 0

for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if (i >> j)  & 1:
            switch[j] = 1
    
    flag = 0
    for j in range(M):
        tmp = 0
        for k in range(1,K[j]+1):
            if switch[S[j][k] - 1] == 1:
                tmp += 1
        
        if tmp % 2 != P[j]:
            flag = 1
            break
    if not flag:
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
S = list([int(i) for i in input().split()] for i in range(M))
p = list(map(int, input().split()))
count = 0

for i in range(2**N):
  onoff = [0]*N
  flag = 0
  for j in range(N):
    if (i >> j) & 1:
      onoff[j] = 1
  for k in range(M):
    tmp = 0
    for l in range(S[k][0]):
      if onoff[S[k][l+1]-1] == 1:
        tmp += 1
    if tmp%2 == p[k]:
      continue
    else:
      flag = 1
      break
    
  if flag == 0:
    count += 1
print(count)

Solution (Python):


n,m=list(map(int, input().split()))
switches=[]
for i in range(m):
    l1=list(map(int, input().split()))[1:]
    s=0
    for i in l1:
        s+=1<<(i-1)
    switches.append(s)
remainders=list(map(int, input().split()))
answer=0
for i in range(1<<n):
    is_all_lighted=True
    for j,s in enumerate(switches):
        if bin(s&i).count("1")%2 != remainders[j]:
            is_all_lighted = False
    if is_all_lighted == True:
        answer+=1
print(answer)

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

ans = 0
for i in range(2**n):
    ls = []
    for j in range(n):
        if (i>>j)&1:
            ls.append(j+1)
    
    flg = 1
    for k in range(m):
        if len(set(s[k])&set(ls))%2==p[k]:
            pass
        else:
            flg = 0
    if flg ==1:
        ans +=1

print(ans)

Solution (Python):
from sys import stdin

N, M = map(int,stdin.readline().rstrip().split())
switchList=[]
for i in range (M):
  switchList.append(list(map(int, stdin.readline().rstrip().split())))
pList = list(map(int, stdin.readline().rstrip().split()))

methodCounter=0
for i in range(2**N):
  lightOnCounter=0
  for j in range (M):
    k = switchList[j][0]
    onCounter=0
    for l in range (1,k+1,1):
      switch=switchList[j][l]
      bit = 1 << switch-1
      if (i & bit) != 0:
        onCounter+=1
    if onCounter %2 == pList[j]:
      lightOnCounter+=1
  if lightOnCounter == M:
    methodCounter+=1
print(methodCounter)

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

ans = 0
for i in range(0,2**n):
	bi_str = format(i, '0'+str(n)+'b')
	
	flag = True
	for j in range(len(s)):
		
		switch = 0
		for x in s[j]:
			if bi_str[x-1] == str(1):
				switch += 1
		
		

		if switch%2 != p[j]:
			flag = False
	if flag:
		ans += 1

print(ans)

Solution (Python):
import sys
import math 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()


N,M = na()
light = []
for i in range(M):
    t = na()
    s = 0
    for i in t[1:]:
        s += 1 << (i-1)
    light.append(s)

ppp = na()
sum_s = 0
for i in range(1<<N):
    t=0
    for s,p in zip(light,ppp):
        if p == bin(i&s).count("1")%2:
            t+=1
    if t == M:
        sum_s+=1
print(sum_s)

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

ans=0
for i in range(1<<N):
    flg=True

    for c,s in enumerate(sw):
        s_on=0
        for bit in s:
            if ((i >> (bit-1)) & 1) == 1:
                s_on+=1
        if s_on%2!=p[c]:
            flg=False

    if flg:
        ans+=1

print(ans)

Solution (Python):
inf = input().split()
N = int(inf[0])
M = int(inf[1])
ls = [[] for i in range(N)]
state = [0 for i in range(M)]
count = 0
log = []

for i in range(M):
    line = input().split()[1:]
    for a in line:
        ls[int(a)-1] += [i]

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

for n in range(2**N):
    s = n
    for m in range(N)[::-1]:
        if n>=(2**m):
            n -= 2**m
            for i in ls[m]:
                state[i] += 1
    for i in range(M):
        if not state[i]%2 == rule[i]:
            break
    else:
        count += 1
    state = [0 for i in range(M)]
print(count)

Solution (Python):
from itertools import product


def solve(string):
    n, m, *ksp = map(int, string.split())
    p = ksp[-m:]
    ans = 0
    for t in product([True, False], repeat=n):
        index = 0
        for i, _p in enumerate(p):
            k = ksp[index]
            use = ksp[index + 1:index + 1 + k]
            index += k + 1
            if sum([t[j - 1] for j in use]) % 2 != _p:
                break
        else:
            ans += 1
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m + 1)])))