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 = [int(x) for x in input().split()]

K = []
S = []

for _ in range(M):
    i = [int(x) for x in input().split()]
    S.append([x-1 for x in i[1:]])

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

ans = 0
for pool in itertools.product(range(2), repeat=N):
    t = [0 for _ in range(M)]
    for i in range(M):
        for j in S[i]:
            if pool[j] == 1:
                t[i] += 1
    if all([x%2==P[i] for i, x in enumerate(t)]):
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
import itertools






def solve():
    k_list = []
    n, m = map(int, input().split())
    for i in range(m):
        row = list(map(int, input().split()))
        k = row[0]
        k_list.append(row[1:])
    p_list = list(map(int, input().split()))

    
    
    

    
    n_all_on = 0

    comb = [[0, 1]] * n
    for pattern in itertools.product(*comb):
        pat_on = True
        for iden in range(m):
            p = p_list[iden]
            on_s_iden = 0
            for isw in k_list[iden]:
                on_s_iden += pattern[isw-1]
            if p != on_s_iden % 2:
                pat_on = False
                break

        if pat_on == True:
            n_all_on += 1

    print(n_all_on)


solve()

Solution (Python):
N, M = map(int, input().split())
s2m = [[]for n in range(N)]
for m in range(M):
    line = list(map(int, input().split()))
    for s in line[1:]:
        s2m[s-1].append(m)
p = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    msc = [0 for m in range(M)]
    bit = str(bin(i))[2:].zfill(N)
    for j, b in enumerate(bit):
        if b == '1':
            for m in s2m[j]:
                msc[m] += 1
    count = 0
    for k, sc in enumerate(msc):
        if sc % 2 == p[k]:
            count += 1
    if count == M:
        ans += 1

print(ans)

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

k = 0
count = 0
for i in range(2**n):
    ans = 1
    for j in range(m):
        ons = sum([int(format(i,'b').zfill(n)[-k]) for k in st[j]])
        
        if not ons%2==p[j]:
            ans=0
    if ans:
        count +=1

print(count)

Solution (Python):
import math
import fractions
import copy

def j(q):
    if q==1: print("YES")
    elif q == 0:print("NO")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def printrow(a):
    for i in range(len(a)):
        print(a[i])
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)



n,m= (int(i) for i in input().split())       








a =[]
for i in range(m):
    adder = [int(i)-1 for i in input().split()]
    adder.pop(0)
    a.append(adder)
sw =  [int(i) for i in input().split()]
ctsw = [0 for i in range(n)]
ctsw[0] = -1
suc = 0
while sum(ctsw)<n:
    p = 0
    ctsw[0]+=1
    if ctsw[p]==2:
        while ctsw[p] == 2:
            ctsw[p] = 0
            p+=1
            ctsw[p]+=1
    for i in range(m):
        use = a[i]
        total = 0
        for k in range(len(use)):
            d = use[k]
            total+=ctsw[d]
        if total%2 != sw[i]: break
        if total%2 == sw[i] and i == m-1:suc+=1
print(suc)

Solution (Python):
n, m = map(int, input().split())
S = []
for _ in range(m):
  s = list(map(int, input().split()))
  s.pop(0)
  S.append(s)
P = list(map(int, input().split()))

ans = 0
for i in range(2 ** n):

  flag = 1
  for j in range(m):

    cnt = 0
    for k in S[j]:
      cnt += (i >> (k - 1)) & 1

    if cnt % 2 != P[j]:
      flag = 0
      break
  if flag == 1:
    ans += 1
    
print(ans)

Solution (Python):
import sys


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

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

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

ans=0
for i in range(2**N):
    tmp=[p[i] for i in range(M)]
    s=bin(i)[2:].zfill(N)
    state=[int(s[i]) for i in range(N)]

    for j in range(M):
            for k in range(1,sw[j][0]+1):
                if state[sw[j][k]-1]==1:
                    tmp[j]=(tmp[j]+1)%2
    
    if max(tmp)==0: ans+=1

print(ans)

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


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

    S.append(s[1:])

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


import itertools
cnt = 0
for tpl in itertools.product([0,1], repeat=N):
    f = True
    for m in range(M):
        c = 0
        for s in S[m]:
            c += tpl[s-1]
        
        if (c%2+P[m])%2 != 0:
            f = False
            break
    if f:
        cnt += 1

print(cnt)

Solution (Python):
import numpy as np
N, M = map(int, input().split())
den = [0 for i in range(M)]
for i in range(M):
    inputlist = list(map(int, input().split()))
    newlist = [k-1 for k in inputlist]
    den[i] = newlist[1:]
p = list(map(int, input().split()))

count = 0
for i in range(2** N):
    sinsu = bin(i)[2:].zfill(N)
    num = np.array([int(k) for k in list(sinsu)])
    now = True
    for j in range(M):
        sumnum = sum(num[den[j]])
        if sumnum % 2 != p[j]:
            now = False
            break
    if now:
        count += 1
print(count)

Solution (Python):

import itertools
MOD = 2  


def solve(N, M, k, s, p):
    count = 0
    bluteforce = list(itertools.product([0, 1], repeat = N))

    for b in range(len(bluteforce)):
        for i in range(M):
            temp = [bluteforce[b][x-1] for x in s[i]]
            if sum(temp) % 2 == p[i]:
                success = 1
                pass
            else:
                success = 0
                break
        if success == 1:
            count += 1
    print(count)


def main():
    
    N, M = map(int, input().split())
    k = []
    s = []
    for i in range(M):
        k_temp, s_temp = input().split(' ', 1)
        k.append(int(k_temp))
        s.append(list(map(int, s_temp.split())))
    p = list(map(int, input().split()))

    solve(N, M, k, s, p)
    pass


if __name__ == '__main__':
    main()

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

k = [list(map(int, input().split()))[1::] for i in range(M)]
p = list(map(int, input().split()))
switches = [format(i, "b").zfill(N) for i in range(2**N)]

ans = 0
for sw in switches:
    allt = True
    for i in range(M):
        sum = 0
        for s in k[i]:
            if(sw[s-1]=="1"):
                sum += 1
        if(sum%2!=p[i]):
            allt = False
            break
    if(allt):
        ans+=1

print(ans)

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

switch = []
for i in range(M):
  ks = input().split()
  k = int(ks[0])
  for j in range(k):
    if j == 0:
      switch.append([int(ks[j + 1]) - 1])
    else:
      switch[-1].append(int(ks[j + 1]) - 1)

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

com = 2 ** N
ans = 0
for i in range(com):
  cnt = 0
  for j in range(M):
    sw_cnt = 0
    for s in switch[j]:
      sw_cnt += int((i % (2 ** (s + 1))) / (2 ** s))
    if sw_cnt % 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 _ in range(M)]
P = list(map(int, input().split(" ")))

s = [set(ks[1:]) for ks in KS]







count = 0
for i in range(1<<N):
    t = set()
    for j in range(N):
        if (i>>j)%2:
            t.add(j+1)
            
    
    if all(len(s_i & t)%2==P[k] for k, s_i in enumerate(s)):
        count += 1
            

print(count)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

n,m = m()

a = []

for i in range(m):
	a.append(l())

p = l()

su = 0
kk = []
for i in range(2**n):
	kk = []
	for j in range(m):
		co = 0
		for k in range(a[j][0]):
			if (i >> (n -(a[j][k+1])) & 1):
				co += 1
		kk.append(co)
	if all(kk[i] % 2 == p[i] for i in range(m)):
		su += 1
print(su)

Solution (Python):

import itertools

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

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

ans = 0

for switch in itertools.product(range(2), repeat=N):
    flg = True
    for i in range(M):
        snum = 0
        for j in range(k[i]):
            if switch[s[i][j]-1]:
                snum += 1
        if snum % 2 == p[i]:
            continue
        else:
            flg = False
            break
    if flg:
        ans += 1

print(ans)

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

ks = []
switch_to_light = [[] for _ in range(N)]

for i in range(M):
    t = list(map(int, input().split()))
    ks.append(list(map(lambda x: x - 1, t[1:])))
for i, k in enumerate(ks):
    for ss in k:
        switch_to_light[ss].append(i)




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


ans = 0
for i in range(1 << N):
    
    cnt = [0] * M
    for j in range(N):
        if (i >> j) & 1:
            
            for light_idx in switch_to_light[j]:
                
                cnt[light_idx] += 1
    flg = True
    for j in range(M):
        if cnt[j] % 2 != p[j]:
            flg = False
            break
    if flg:
        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()))
odd_list = []
even_list = []
for i in range(m):
    k = ks_list[i][0]
    s_list = ks_list[i][1:]
    p = p_list[i]

ans = 0
for i in range(2 ** n):
    on_list = [False] * n
    for j in range(n):
        if ((i >> j) & 1):
            on_list[j] = True
    ok = True
    for j in range(m):
        k = ks_list[j][0]
        s_list = ks_list[j][1:]
        p = p_list[j]
        count = 0
        for s in s_list:
            if on_list[s-1]:
                count += 1
        if count % 2 != p:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

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

ans = 0
for i in range(2**N):
    is_correct = True
    for p in range(M):
        light = 0
        for sw in switches[p]:
            light += 1 if (i>>(sw-1)) & 1 else 0
        if light % 2 != extras[p]:
            is_correct = False
            break
    if is_correct:
        ans += 1
print(ans)

Solution (Python):
N,M = map(int, input().split(" "))
masks = []
for _ in range(M):
    mask = 0
    for s in list(map(int, input().split(" ")))[1:]:
        mask += 1 << (s-1)
    masks.append(mask)
p = list(map(int, input().split(" ")))

ans = 0
for d in range(1 << N):
    flg = True
    for i in range(M):
        if bin(d & masks[i]).count("1") % 2 != p[i]:
            flg = False
            break
    if flg: ans += 1
print(ans)

Solution (Python):
import numpy as np
from itertools import chain,combinations

words = lambda t : list(map(t, input().split()))

n,m = words(int)
ks = []
for i in range(m):
  ks.append(words(int))
  ks[i].pop(0)

ms = words(int)



def powerset(it):
  s = list(it)
  return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

ans = 0
for s in powerset([i+1 for i in range(n)]):
  n_on = 0
  for k,mods in zip(ks,ms):
    n_inc = 0
    for ink in k:
      if ink in s:
        n_inc += 1
    if n_inc % 2 == mods:
      n_on += 1
  if n_on == m:
    ans += 1

print(ans)

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

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

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


ans = 0

for i in range(2 ** n):
    flg = 0
    onswitchkosuu = [0] * m
    for j in range(n):  
        if ((i >> j) & 1):  
            for k in range(m):  
                if j+1 in s[k]:
                    onswitchkosuu[k] += 1

   
    

    for j in range(m):
        if onswitchkosuu[j] % 2 != p[j]:
            flg = 1

    if flg == 0:
        ans += 1

print(ans)

Solution (Python):
from collections import deque

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

s_m = []
for _ in range(M):
    flag = True
    num = 0
    for s in input().split():
        if flag:
            flag = not flag
        else:
            s = int(s)
            num += 2**(s-1)
    s_m.append(num)

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



cnt = 0
for i in range(2**N):
    flag = True
    for j in range(len(s_m)):
        n = s_m[j]
        n &= i
        tf = True if p[j] == 0 else False
        
        for _ in range(N):
            if n & 1 == 1:
                tf = not tf
            n >>= 1
        if not tf:
            flag = False
            break
    if flag:
        cnt += 1

print(cnt)

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

ans=0
for i in range(1<<N):
    flag=0
    for j in range(M):
        t=0
        for k in range(ks[j][0]):
            t+= 1 & (i>>ks[j][k+1]-1)
        if t%2!=p[j]:
            flag=1
            break
    if flag:
        continue
    ans+=1
print(ans)

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

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

ans = 0
for p in product([0,1],repeat=N):
    can = 0
    for i in range(M):
        res = 0
        for s in S[i]:
            if p[s-1] == 1:
                res += 1
        res %= 2
        if res == P[i]:
            can += 1
    if can == M:
        ans += 1

print(ans)

Solution (Python):
from itertools import product
N, M = list(map(int, input().split()))
light_sw = []
for _ in range(M):
    light_sw.append(list(map(lambda x: x-1, map(int, input().split()[1:]))))
P = list(map(int, input().split()))

count = 0
pro = product([0, 1], repeat=N)
for pr in pro:
    for i, sw in enumerate(light_sw):
        sw_sum = 0
        flag = True
        for k in sw:
            sw_sum += pr[k]
        if sw_sum%2 != P[i]:
            flag = False
            break
    if flag:
        count += 1
print(count)

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

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

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

result = 0
for i in itertools.product([0,1], repeat=N):
  for j in range(M):
    re = 0
    for s in lamp[j]:
      re += i[s-1]
    if re % 2 != P[j]:
      break
  else:
    result += 1
print(result)

Solution (Python):
N,M = map(int,input().split())
hoge = []
for i in range(M):
    K = input().split()
    hoge.append(K)
P = input().split()
count = 0
for i in range(2**N):
    L = bin(i)[2:]
    leng = len(L)
    for pu in range(leng,N):
        L = "0" + L
    for j in range(M):
        hu = 0
        for a in hoge[j][1:]:
            if L[int(a)-1] == "1":
                hu += 1
        if hu % 2 != int(P[j]):
            break
        if j == M-1:
            count += 1
print(count)

Solution (Python):
import itertools as it

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

s = []

for i in range(m):

    k, *temp = map(int, input().split())

    s.append(set(temp))

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

ans = 0

if all([temp == 0 for temp in p]):
    ans += 1

for i in range(1, n + 1):

    for comb in it.combinations(list(range(1, n + 1)), i):

        flag = [False] * m

        for j in range(m):

            count = 0

            for k in range(i):

                if comb[k] in s[j]:
                    count += 1

            if count % 2 == p[j]:
                flag[j] = True

        if all(flag):
            ans += 1

print(ans)

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

K, S_list = list(), list()
for i in range(M):
  k, *S = map(int, input().split())
  
  S_list.append(set(S))
P = list(map(int, input().split()))


def search(N, status=set()):
  if N == 0:
    yield status
  else:
    yield from search(N-1, status=status | {N})
    yield from search(N-1, status=status)


ans = 0
for status in search(N):
  for p, S in zip(P, S_list):
    if len(S & status) % 2 != p:
      break
  else:
    ans += 1
print(ans)

Solution (Python):
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import copy


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

    all_list = []
    for i in range(n):
        i = str(i)
        for j in copy.deepcopy(all_list):
            all_list.append(j+i)
        all_list.append(i)
    all_list.append('')

    connects = [None]*m

    for i in range(m):
        connects[i] = list(input().split())[1:]

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

    ans = 0

    for pattern in all_list:
        for connect, leave in zip(connects, leaves):
            count = 0
            for num in connect:
                if str(int(num)-1) in pattern:
                    count += 1
            if count%2 != leave:
                break
        else:
            ans += 1

    print(ans)

Solution (Python):
N, M = [int(n) for n in input().split()]
S = [[int(n) for n in input().split()][1:] for _ in range(M)]
P = [int(n) for n in input().split()]

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

def inc(i):
    if i == N:
        return False
    F[i] += 1
    if F[i] == 2:
        F[i] = 0
        return inc(i + 1)
    return True

def check(i):
    f_cnt = 0
    for j in S[i]:
        f_cnt += F[j-1]
    if f_cnt % 2 == P[i]:
        return True
    return False

cnt = 0
while True:
    flag = True
    for i in range(M):
        if not check(i):
            flag = False
            break
    if flag:
        cnt += 1
    if not inc(0):
        break

print(cnt)

Solution (Python):
import sys
import itertools
def input(): return sys.stdin.readline().strip()

mi = lambda: map(int, input().split())
li = lambda: list(map(int, input().split()))

N, M = mi()
S = [None] * N
B = [li() for _ in range(M)]
P = li()

count = 2**N
for s in itertools.product((0,1), repeat=N):
  for i in range(M):
    if sum([s[si-1] for si in B[i][1:]]) % 2 != P[i]:
      count -= 1
      break

print(count)

Solution (Python):
import sys
sys.setrecursionlimit(2000)

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

def rec(k, lst):
    if k == N:
        b = [0] * M
        for i in range(N):
            if lst[i] == 0:
                continue
            for j in range(M):
                if i + 1 in sw[j][1:]:
                    b[j] += 1
        
        return M == sum([b[i] % 2 == p[i] for i in range(M)])
    return rec(k + 1, lst + [0]) + rec(k + 1, lst + [1])

a = rec(1, [0])
b = rec(1, [1])
print(a + b)

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

ans = 0
for i in range(2**n):
    switch = [int(bin(i+2**n)[j+3]) for j in range(n)]
    condition = []
    for k in range(m):
        num = 0
        for l in range(ks[k][0]):
            if switch[ks[k][l+1]-1]:
                num += 1
        if num % 2 == p[k]:
            condition.append(True)
        else:
            condition.append(False)
    flag = 1
    for x in range(m):
        flag *= condition[x]
    if flag == True:
        ans += 1
print(ans)

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsm = lambda: map(str, sys.stdin.readline().split())

n, m = nm()
lis = [[] for _ in range(m)]
k = [0 for _ in range(m)]
for i in range(m):
    tmp = nl()
    k[i] = tmp[0]
    lis[i] = tmp[1:]
p = nl()
ans = 0
for i in range(2 ** n):
    bit = bin(i)[2:].zfill(n)
    ccnt = 0
    for j in range(m):
        cnt = 0
        for ll in lis[j]:
            if bit[ll - 1] == '1':
                cnt += 1
        if cnt % 2 == p[j]:
            ccnt += 1
    if ccnt == m:
        ans += 1
print(ans)

Solution (Python):
import numpy as np
import itertools
N,M=[int(i) for i in input().split(" ")]
k_dict={}
for i in range(M):
    _in=[int(j)-1 for j in input().split(" ")]
    k=_in[0]
    s=_in[1::]
    k_dict[i]=s



p=np.asarray([int(i) for i in input().split(" ")])

def _switch(pattern):
    lamps=np.zeros(M)
    for i,pat in enumerate(pattern):
        if pat==0:
            continue
        for key in k_dict:
            if i in k_dict[key]:
                lamps[key]+=1



    return np.sum(lamps%2 == p)==M


retval=0
for i in itertools.product([0,1], repeat=N):
    retval+=_switch(i)
print(retval)

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def bin_count(x, N):
    count = 0
    for i in range(N):
        mask = 0x01 << i
        if (x & mask) != 0:
            count += 1
    return count


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]
    mask_list = []
    for i in range(M):
        input_raw = read_func().strip().split()
        [K] = [int(input_raw[0])]
        mask = 0
        for j in range(K):
            mask += 0x01 << (int(input_raw[j + 1]) - 1)
        mask_list.append(mask)


    input_raw = read_func().strip().split()
    P_list = [int(input_raw[i]) for i in range(M)]

    ans = 0
    for i in range((0x01 << N)):
        is_ok = True
        for j in range(len(mask_list)):
            mask = mask_list[j]
            if (P_list[j] != (bin_count(mask & i, N)%2)):
                is_ok = False
                break
        if is_ok == True:
            ans += 1
    print ans




if __name__ == '__main__':
    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()))
check_list = []
for i in range(2 ** n):
    a = bin(i)[2::]
    while len(a) < n:
        a = "0" + a
    
    check_list.append(a)


num = 0
ans = 0
for i in check_list:
    num = 0
    key = 1
    for j in ks:
        cnt = 0
        
        for k in range(1, len(j)):
            
            
            if i[j[k] - 1] == "1":
                
                cnt += 1
        if cnt % 2 != p[num]:
            
            key = 0
            break
        num += 1
    if key:
        ans += 1
print(ans)

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

c = 0
q = 0
for i in range(2**n):
    t = format(i,"010b")
    s = t[10-n:]
    r = 0
    for j in range(m):
        for u in range(k[j][0]):
            q += int(s[k[j][u+1]-1])
        if q % 2 == p[j]:
            q = 0
            continue
        else:
            q = 0
            r = 1
            break
    if r == 0:
        c += 1

print(c)

Solution (Python):
from itertools import permutations

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

ans = [0]
def dfs(l, depth):
    if depth== 0:
        for i in range(m):
            cnt = 0
            for j in ss[i]:
                if l[j-1]:
                    cnt += 1
            if cnt%2 != p[i]:
                return
        ans[0] += 1
        return
    q = l[::]
    q[depth-1] = 1
    dfs(l[::], depth-1)
    dfs(q, depth-1)
dfs([0]*n, n)
print(ans[0])

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

KS = []
for _ in range(M):
    ks = list(map(int, input().split()))
    KS.append(tuple([ks[0], set(ks[1:])]))

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

cnt = 0
for n in range(2**N):
    on_switchs = set()
    n_tmp = n
    for i in range(0, N):
        if n_tmp == 0:
            break
        else:
            if n_tmp % 2 == 1:
                on_switchs.add(N-i)
            n_tmp //= 2
    
    for m in range(M):
        if (len(on_switchs & KS[m][1]) % 2) != P[m]:
            break
    else:
        cnt += 1
            
print(cnt)

Solution (Python):
N, M = map(int, input().split())
S = [0] * M
for i in range(M):
    _, *s, = map(int, input().split())
    for v in s:
        S[i] = S[i] | (1 << (v - 1))

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

ans = 0
for p in range(2**N):
    ok = True
    for i in range(M):
        b = format(p & S[i], 'b')
        if b.count('1') % 2 != P[i]:
            ok = False
            break
    if ok:
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
cond = [0] * M
for i in range(M):
    cond[i] = list(map(int, input().split()))
p = list(map(int, input().split()))

ans = 0
for i in range(2**N):
    switch = bin(i)[2:].zfill(N)
    ok = 1
    for j in range(M):
        sum_s = 0
        for k in range(cond[j][0]):
            if switch[cond[j][k+1] - 1] == '1':
                sum_s += 1
        if sum_s % 2 != p[j]:
            ok = 0
    if ok:
        ans += 1
print(ans)

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

cnt = 0
for i in range(2**N):
    on_off = list(map(int,list(bin(i)[2:].zfill(N))))
    for j in range(M):
        on = 0
        for index in sw_list[j]:
            on += on_off[index-1]
        if on%2 != zero_or_one[j]:
            break
    else:
        cnt += 1
print(cnt)

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

switch = []
for i in range(0, m):
    s = map(int, raw_input().split(" "))
    switch.append(s[1:])

power = map(int, raw_input().split(" "))

ans = 0
for state_int in range(0, 2 ** n):
    format_str = "{:0" + str(n) + "b}"
    state_bin = format_str.format(state_int)
    

    state = [0 for j in range(0, len(state_bin))]
    for i in range(0, len(state)):
        if state_bin[i] == "1":
            state[i] = True
        else:
            state[i] = False

    
    on = True
    for s in range(0, m):
        ts = switch[s]
        count = 0

        for j in range(0, len(ts)):
            if state[ts[j] - 1]:
                count += 1

        if power[s] != count % 2:
            on = False
            break

    if on:
        
        ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
s = [sum(list(map(lambda x: 2**(int(x) - 1), input().split()[1:]))) for _ in range(m)]
p = list(map(int, input().split()))

ans = 0
for i in range(2**n):
    cnt = 0
    for j in range(m):
        if sum([((i & s[j]) >> k) % 2 for k in range(n)]) % 2 == p[j]:
            cnt += 1
    if cnt == m:
        ans += 1
print(ans)

Solution (Python):


N, M = map(int, input().split())
sw = [[int(_)-1 for _ in input().split()] for i in range(M)]
p = [int(_) for _ in input().split()]

def rec(n, onoff, lmp):
    if n < N:
        onoff[n] = True
        s = rec(n+1, onoff, lmp)
        onoff[n] = False
        s += rec(n+1, onoff, lmp)
        return s
    else:
        sm = 0
        for i in range(M):
            r = 0
            for j in sw[i][1:]:
                if onoff[j]:
                    r+=1
            if r % 2 == lmp[i]:
                sm += 1
        if sm == M:
            return 1
        else:
            return 0

onoff = [False for _ in range(N)]
print(rec(0, onoff, p))

Solution (Python):
N,M=map(int,input().split())
A=[]
for i in range(M):
  a=[int(i)-1 for i in input().split()]
  A.append(a[1:])
P=[int(i) for i in input().split()]
ans=0
for i in range(1<<N):
  F=True
  
  for a in range(M):
    r=0
    for s in A[a]:
      r+=(((1<<s)&(i))>>s)
    
    if P[a]!=r%2:
      F=False
      break
  if F:
    ans+=1
print(ans)

Solution (Python):
def make_cands(num, cands=[[0],[1]]):
    if len(cands[0]) == num:
        return cands
    else:
        newcands = []
        for cand in cands:
            newcands.append(cand+[0])
            newcands.append(cand+[1])
        return make_cands(num, newcands)

N,M = map(int, input().split())
switches = []
for _ in range(M):
    ks = list(map(int, input().split()))
    switches.append(ks[1:])
p = list(map(int, input().split()))
ans = 0
ress = make_cands(N)
for res in ress:
    tentou = 0
    for sw_i, sw in enumerate(switches):
        cnt = 0
        for num in sw:
            cnt += res[num-1]
        tentou += 1 if cnt % 2 == p[sw_i] else 0
    if tentou == M:
        ans += 1

print(ans)

Solution (Python):
import math

n,m = list(map(int, input().split()))
switchlist = []

for i in range(m):
    a = list(map(int, input().split()))
    switchlist.append([])
    for j in range(a[0]):
        switchlist[i].append(a[j+1])
switchval = list(map(int, input().split()))

ans = 0

    
for i in range(2**n):
    zeroone=[]
    ii=i
    flag=1
    for j in range(n):
        zeroone.append(ii%2)
        ii=ii//2
    
    for j in range(m):
        count=0
        for k in range(len(switchlist[j])):
            
            count+=zeroone[switchlist[j][k]-1]
        
        if(count%2 != switchval[j]):
            flag=0
            
    if(flag==1):
        ans+=1
        
print(ans)