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

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

ans = 0

for bit in range(1<<n):
  on = 0
  for i in range(m):
    numon = 0
    k = k_s[i][0]
    s = k_s[i][1:]
    for j in range(k):
      mask = 1<<(s[j]-1)
      if mask&bit:
        numon += 1
    if numon%2 == p[i]:
      on += 1
  if on == m:
    ans += 1

print(ans)

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

index = [i for i in range(1, n+1)]
counter = 0

for i in range(2**n):
  cand_list = []
  flg = True
  
  for j in range(n):
    if i&1<<j:
      cand_list.append(index[j])
  
  for k_i, k in enumerate(K):
    if len(set(cand_list)&set(k))%2!=P[k_i]:
      flg = False
      break
  if flg:
    counter += 1
    
print(counter)

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

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

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

switch = [0]*N

res = 0
for i in range(1<<N):
    div = i
    for j in range(N):
        switch[j] = div % 2
        div //= 2

    on = True
    for l in range(M):
        s_state = 0
        for s_check in s[l]:
            s_state ^= switch[s_check-1]
        if s_state != p[l]:
            on = False
    
    if on:
        res += 1

print(res)

Solution (Python):

from itertools import product

def judge(co,m,k,s,p):
    flag = True
    for i in range(m):
        _s = s[i]
        _p = p[i]
        _k = k[i]
        amount = sum([co[_s[j]-1] for j in range(_k)])
        if amount % 2 != _p:
            flag = False
    return flag 



def solve(n,m,k,s,p):
    b = product((0,1),repeat=n)
    c = 0
    for co in b:
        if judge(co,m,k,s,p):
            c += 1
    return c



def main():
    N,M = map(int,input().split())
    k = []
    s = []
    for _ in range(M):
        tmp = list(map(int,input().split()))
        k.append(tmp[0])
        s.append(tmp[1:])
    p = list(map(int,input().split()))
    print(solve(N,M,k,s,p))
    return

if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
k , s = [], []
for m in range(M):
  line = list(map(int, input().split()))
  k.append(line[0])
  s.append(line[1:])
p = list(map(int, input().split()))
light_up = [0] * M
ans = 0

for bit in range(0, 1<<N):
  bit_str = format(bit, 'b').zfill(N)
  for m in range(M):
    counter = 0
    for index in s[m]:
      counter += int(bit_str[index-1])
    if counter%2 == p[m]:
      light_up[m] = 1
    else:
      light_up[m] = 0
  if sum(light_up) == M:
    ans += 1
print(ans)

Solution (Python):
import numpy as np
from itertools import combinations
n,m = map(int,input().split())
card =[[0]*n for _ in range(m)]
for i in range(m):
    switch = list(map(int,input().split()))[1:]
    for k in switch:
        card[i][k-1] = 1





ans =list(map(int,input().split()))
cnt=0
from itertools import combinations

for epoch in range(1,n+1):
    
    for j in combinations(range(1,n+1),epoch):
        sco =[]
        for lisa in card:
            score =0
            for l in j:
                score += lisa[l-1]
                
            sco.append(score)
        
        if list(np.array(sco)%2) == ans:
            cnt+=1
    

if ans == [0]*m:
    cnt+=1
        
print(cnt)

Solution (Python):
import sys
from itertools import product
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    S = [list(map(int, input().split())) for _ in range(m)]
    P = list(map(int, input().split()))

    res = 0
    for pattern in product([0, 1], repeat=n):
        total = 0
        for i in range(m):
            cnt = 0
            for idx, p in enumerate(pattern):
                if p == 1 and idx + 1 in S[i][1:]:
                    cnt += 1
            if cnt % 2 == P[i]:
                total += 1
        if total == m:
            res += 1
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
def dfs(A):
    global cnt

    if len(A) == n:
        ans = [0 for i in range(m)]
        for i, a in enumerate(A):
            if a:
                for j in range(m):
                    if i+1 in s[j]:
                        ans[j] += 1
        for x, y in zip(p, ans):
            if x != y%2:
                break
        else:
            cnt += 1
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

n, m = map(int, input().split())
s = [list(map(int, sys.stdin.readline().split()))[1:]  for x in range(m)]
p = list(map(int, sys.stdin.readline().split()))
cnt = 0
dfs([])
print(cnt)

Solution (Python):
def dfs(A):
    global cnt

    if len(A) == n:
        ans = [0 for i in range(m)]
        for i, a in enumerate(A):
            if a:
                for j in range(m):
                    if i+1 in s[j]:
                        ans[j] += 1
        for x, y in zip(p, ans):
            if x != y%2:
                break
        else:
            cnt += 1
        return
    for v in range(2):
        A.append(v)
        dfs(A)
        A.pop()

n, m = map(int, input().split())
s = [list(map(int, input().split()))[1:]  for _ in range(m)]
p = list(map(int, input().split()))
cnt = 0
dfs([])
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
k = [0 for _ in range(m)]
s = [[] for _ in range(m)]
for i in range(m):
  k[i],*s[i] = map(lambda x:int(x)-1,input().split())
p = list(map(int,input().split()))
ans = 0
for i in range(m):
  ds = ["0"]*n
  for j in s[i]:
    ds[j] = "1"
  s[i] = int("".join(ds),2)
for i in range(2**n):
  for j in range(m):
    if not bin(i&s[j]).count("1")%2 == p[j]:
      break
  else:
    ans += 1
print(ans)

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

S = []
for i in range(m):
    s = list(map(int, input().split()))
    S.append(s[1:])
    
P = [int(i) for i in input().split()]
    
A = [0, 1]
ans = 0
for a in itertools.product(A, repeat = n):
    flag = 0
    for j in range(m):
        cnt = 0
        for s in S[j]:
            if a[s - 1] == 1:
                cnt += 1
        if cnt % 2 != P[j]:
            flag = 1
    if flag == 0:
        ans += 1
        
print(ans)

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

all_on_cnt = 0

for i in range(2**n):
  light_list = [0 for _ in range(m)]
  on_off = [0 for _ in range(n)]
  
  cnt = 0
  while i!=0:
    on_off[cnt] = i%2
    i//=2
    cnt+=1
  
  for j in range(m):
    tmp = switch_list[j]
    on_cnt = 0
    for k in tmp:
      on_cnt += on_off[k-1]
    if on_cnt%2==p_list[j]:
      light_list[j]=1
  if sum(light_list)==m:
    all_on_cnt+=1
print(all_on_cnt)

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

switches = []
for index in range(m):
    switch = input().split()
    switches.append(list(map(int, switch[1:])))
passes = list(map(int, input().split()))

output = 0
for index in range(2 ** n):

    light = 0
    for mm in range(m):
        count = 0
        for shift in switches[mm]:
            if (index >> shift - 1) & 1:
                count += 1
        if count % 2 == passes[mm]:
            light += 1
    
    if light == m:
        output += 1

print(output)

Solution (Python):
N,M = map(int, input().split())
K = [0]*M
S = [None]*M
for j in range(M):
    lis = list(map(int, input().split()))
    K[j] = lis.pop(0)
    S[j] = lis
    
P = list(map(int, input().split()))

count = 0
for b in range(2**N):
    onoff = [b>>i & 1 for i in range(N)]
    flag = True
    for m in range(M):
        slist = S[m]
        ON = 0
        for s in slist:
            ON += onoff[s-1]
        if ON % 2 != P[m]:
            flag = False
            break
    if flag:
        count += 1

print(count)

Solution (Python):
n,m=map(int,input().split())
sw=[[] for _ in range(m)]
for _ in range(m):
    temp=list(map(int,input().split()))
    sw[_]=temp[1:]
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for l,s in enumerate(sw):
        cnt=0
        for k in s:
            if temp[k-1]==1: cnt+=1
        if p[l]!=cnt%2:
            flag=0
            break
    if flag: ans+=1
print(ans)

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

ans=0
for i in range(2**n):
    temp=[0]*n
    for j in range(n):
        if i&1: temp[j]=1
        i>>=1
    flag=1
    for l,s in enumerate(sw):
        cnt=0
        for k in s:
            if temp[k-1]==1: cnt+=1
        if p[l]!=cnt%2:
            flag=0
            break
    if flag: ans+=1
print(ans)

Solution (Python):
import itertools

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 itertools.product(range(2), repeat=N):
    cnt = [0 for _ in range(M)]  
    for c, k in enumerate(KS):  
        for j in k[1:]:
            j -= 1
            if i[j] == 1:
                cnt[c] += 1

    for m, c in enumerate(cnt):
        if c % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]
S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]


def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)
    for light_idx in range(num_of_lights):
        
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    
    switch_on_result = rec(switch_idx + 1, _lights)
    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)

Solution (Python):
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]

S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]




def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)

    for light_idx in range(num_of_lights):
        
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    

    switch_on_result = rec(switch_idx + 1, _lights)

    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)

Solution (Python):
import copy

num_of_switch, num_of_lights = [int(_) for _ in input().split()]


def toSwitch(xs):
    xs[1:]


S = [[int(s) - 1 for s in input().split()[1:]] for i in range(num_of_lights)]
P = [_ == "1" for _ in input().split()]




def rec(switch_idx, lights):
    if switch_idx == num_of_switch:
        if lights == P:
            return 1
        else:
            return 0

    switch_off_result = rec(switch_idx + 1, lights)

    _lights = copy.deepcopy(lights)

    for light_idx in range(num_of_lights):
        
        is_connect = switch_idx in S[light_idx]
        if is_connect:
            _lights[light_idx] = not _lights[light_idx]

    

    switch_on_result = rec(switch_idx + 1, _lights)

    return switch_off_result + switch_on_result


ans = rec(0, [False] * num_of_lights)
print(ans)

Solution (Python):
def switch_combination_of_light_on():
    
    N, M = map(int, input().split())
    K = list()
    S = list()
    for _ in range(M):
        dummy = list(map(int, input().split()))
        K = dummy.pop(0)
        S.append(dummy)
    P = list(map(int, input().split()))
    
    result = 0
    for bit in range(1 << N):
        right_on = False
        for i in range(M):
            count = 0
            for j in S[i]:
                if bit & (1 << j - 1):
                    count += 1
            if count % 2 == P[i]:
                right_on = True
            else:
                right_on = False
                break
        if right_on:
            result += 1
    
    print(result)

switch_combination_of_light_on()

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)



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




readline = sys.stdin.readline

KS = [[int(i) for i in readline().split()] for _ in range(m)]
P = [int(i) for i in readline().split()]

import itertools

L = list(itertools.product([0,1], repeat=n))

ans = 0

for l in L:
    for ks, p in zip(KS, P):
        tmp = sum([l[i-1] for i in ks[1:]])
        if tmp%2 == p:
            pass
        else:
            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()))

ans = 0
for i in range(2**N):
    switches = bin(i)[2:].zfill(N)
    for j in range(M):
        _, *S = KS[j]
        on = 0
        for k, s in enumerate(switches, 1):
            if s == '1' and k in S:
                on += 1
        if on % 2 != P[j]:
            all_light_on = False
            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()))

ans = 0
for i in range(2**N):
    switches = bin(i)[2:].zfill(N)
    all_light_on = True
    for j in range(M):
        _, *S = KS[j]
        on = 0
        for k, s in enumerate(switches, 1):
            if s == '1' and k in S:
                on += 1
        if on % 2 == P[j]:
            continue
        else:
            all_light_on = False
            break
    if all_light_on:
        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()))
ans = 0
for i in range(2**N):
    count = 0
    on_or_off = [0]*M 
    for j in range(N):
        if(i>>j)&1:
            for k in range(M):
                if j+1 in K[k][1:]:
                    on_or_off[k] += 1
    for l in range(M):
        if on_or_off[l]%2==P[l]:
            count += 1
    if(count == M):
        ans += 1
print(ans)

Solution (Python):
from itertools import product
n, m = map(int,input().split())
S = []
for i in range(m):
    s = list(map(int,input().split()))
    S.append(s[1:])
p = list(map(int,input().split()))
ans = 0
for c in product([0, 1], repeat = n):
    ok = True
    for j in range(m):
        sm = 0
        for k in S[j]:
            sm += c[k-1]
        if sm % 2 != p[j]:
            ok = False
            break
    if ok:
        ans += 1
print(ans)

Solution (Python):
N,M = list(map(int,input().split()))
KS = [list(map(int,input().split())) for _ in range(M)]
P = list(map(int,input().split()))
ans = 0
for bit in range(1<<N):
    for i,ks in enumerate(KS):
        SUM = 0
        for s in ks[1:]:
            if bit & (1<<(s-1)):
                SUM += 1
        if SUM%2 != P[i]:
            break
    else:
        ans += 1
print(ans)

Solution (Python):
import numpy as np
import itertools

N, M = [int(n) for n in input().split()]

config = np.zeros((M, N)).astype(int)

for i in range(M):
    switches = [int(n) for n in input().split()]
    for switch in switches[1:]:
        config[i][switch - 1] = 1

P = np.asarray([int(n) for n in input().split()], dtype=int).reshape((M, 1))

bits = itertools.product((0,1), repeat=N)

count = 0

for bit in bits:
    bit_vect = np.asarray(bit, dtype=int).reshape((N, 1))
    if np.array_equal(np.dot(config, bit_vect) % 2, P):
        count += 1

print(count)

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

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

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

for i in range(2 ** n):
    tmp = [0] * n
    flg = False
    for j in range(n):
        if i >> j & 1:
            tmp[j] = 1
    for i, s in enumerate(l):
        cnt = sum([tmp[e-1] for e in s])
        if cnt % 2 != p[i]:
            flg = True
            break
    if not flg:
        ans += 1

print(ans)

Solution (Python):
N,M=map(int,input().split())
ans=0
S=[]
for i in range(M):
    s=list(map(int,input().split()))
    K=s.pop(0)
    S.append(s)
P = list(map(int, input().split()))
for i in range(1<<N):
    ok=True
    for j in range(M):
        cnt=0
        for s in S[j]:
            if ((i>>s-1)&1):
                cnt+=1
        if cnt%2!=P[j]:
            ok=False
    if ok:
        ans+=1
print(ans)

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

def rec(A, c):
  if len(A) == n:
    count_m = 0
    for l in range(m):
      list_k = k[l]
      count = 0
      for j in range(1, list_k[0] + 1):
        if A[list_k[j] - 1] == 1:
          count += 1
      if p[l] == (count%2):
        count_m += 1
    if(count_m == m):
      c += 1
    return c
  
  for i in range(2):
    A.append(i)
    c = rec(A, c)
    A.pop()

  return c

print(rec([], check))

Solution (Python):
n,m=map(int,input().split())
S = []
for _ in range(m):
  t = list(map(int,input().split()))[1:]
  t = [v-1 for v in t]
  S.append(t)
p = list(map(int,input().split()))

cnt = 0
for i in range(2**n):
  ok = True
  for j,s in enumerate(S):
    l = 0
    for v in s:
      if (i>>v) & 1: l+=1
    if l%2 != p[j]:
      ok = False
      break
  if ok:
    cnt += 1
print(cnt)

Solution (Python):
import numpy as np

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

cnt = 0
for i in range(2**N):
  cnt += np.prod([
    sum([int(bin(i)[2:].zfill(N)[s-1]) for s in S[j][1:]])%2 == P[j]
    for j in range(M)
  ])
print(cnt)

Solution (Python):
import sys
import itertools

import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

ans = 0
for bit in range(2 ** N):
    ons = 0
    for i in range(M):
        total = K[i]
        for j in S[i]:
            if bit >> (j - 1) & 1 == 0:
                total -= 1
        if total % 2 == P[i]:
            ons += 1
    if ons == M:
        ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
li=[]
for i in range(m):
  dk,*d=list(map(int,input().split()))
  li.append(d)
p=list(map(int,input().split()))
ans=0
for i in range(2**n):
  sw=bin(i)[2:].zfill(n)
  for j in range(m):
    cnt=0
    for k in li[j]:
      if sw[k-1]=='1':
        cnt+=1
    if cnt%2!=p[j]:
      break
  else:ans+=1
print(ans)

Solution (Python):
ans = 0
def solve(balb, p, S, N, M):
    if len(S) == N:
        global ans

        up = 0
        for i in range(M):
            on = 0
            for j in balb[i]:
                if S[j] == "1":
                    on += 1

            if (on % 2 == p[i]):
                up += 1

        if up == M:
            ans += 1
        
    else:
        solve(balb, p, S + "1", N, M)
        solve(balb, p, S + "0", N, M)

def main():
    N, M = map(int, input().split())
    balb = list()

    for i in range(M):
        sw = [int(a) - 1 for a in input().split()]
        balb.append(sw[1:])

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

    solve(balb, p, "", N, M)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(m)]
di = list(map(int,input().split()))
q = 0
for i in range(2**n):
    a = [0]*n
    for j in range(n):
        if (i>>j)&1:
            a[j] = 1
    p = 0
    for k in range(m):
        s = 0
        for l in ls[k][1:ls[k][0]+1]:
            s += a[l-1]
        if s%2 != di[k]:
            p = 1
    if p == 0:
        q += 1
print(q)

Solution (Python):
import itertools
count =0
ans=0
n,m = map(int,input().split())
num=[0,1]
pattern = list(itertools.product(num, repeat=n))
lists =[]
switches = [1]*n
onoff = [0]*m
for i in range(m):
    lists.append(list(map(int,input().split())))
key_value = list(map(int,input().split()))
for l in pattern:
    switches = list(l)
    onoff = [0]*m
    for j in range(m):
        count=0
        for k in lists[j][1:]:
            if switches[k-1] == 1:
                count += 1
        if count %2 == key_value[j]:
            onoff[j] = 1
        else:
            break
    if not 0 in onoff:
        ans += 1

print(ans)

Solution (Python):
def main():
    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):
        state = [0] * N
        flag = True
        for j in range(N):
            if (i >> j) & 1:
                state[j] = 1
        for k in range(M):
            cnt = 0
            for l in s[k]:
                cnt += state[l-1]
            if cnt%2 == p[k]:
                continue
            else:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)
                
if __name__  == '__main__':
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    
    s = []
    for i in range(m):
        x = list(map(int, input().split()))
        
        y = 0
        for j in x[1:]:
            y |= 1 << (j - 1)  
        s.append(y)
    p = list(map(int, input().split()))

    res = 0
    for bit in range(1 << n):
        all_on = True
        for i in range(m):
            n_on = bin(s[i] & bit).count('1')
            if n_on % 2 != p[i]:
                all_on = False
                break
        if all_on:
            res += 1

    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, M = map(int, readline().split())
    S = [0] * M
    for i in range(M):
        k, *S[i] = [int(s) - 1 for s in readline().split()]
    P = list(map(int, readline().split()))

    ans = 0
    for bit in range(1 << N):
        ok = True
        for j in range(M):
            lit = sum(1 for s in S[j] if bit & (1 << s))
            if lit % 2 != P[j]:
                ok = False
                break
        if ok:
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):

from itertools import product
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
num_suitch =[-1]*M
switch =[[]for i in range(M)]
for i in range(M):
    k,*s = (int(i) for i in input().split())
    num_suitch[i] =k
    switch[i] =s
p = list(map(int, input().split()))


count =0
for on in product([0,1],repeat=N): 
    light =[0]*M
    index_on =[i+1 for i, x in enumerate(on) if x == 1] 
    for j in range(M):                      
        l =set(index_on) & set(switch[j])
        if len(l) %2 ==p[j]:
            light[j] =1
    if sum(light) ==M:
        count +=1
print(count)

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

for i in range(1 << n):
    switch = set()
    for j in range(n):
        if (i >> j)&1:
            switch.add(j+1)
    for k in range(m):
        point = 0
        for l in li[k]:
            if l in switch:
                point += 1
        if point%2 != p[k]:
            break
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools

def main():
    n,m=map(int,input().split())
    k = []
    for _ in range(m):
        k.append(list(map(int, input().split())))
    p = list(map(int, input().split()))
    count = 0
    for s in itertools.product([0,1], repeat=n):
        for i,kk in enumerate(k):
            if not is_on(s, kk[1:], p[i]):
                break
        else:
            
            count += 1
    print(count)

def is_on(s, cond, p):
    count = 0
    for c in cond:
        count += s[c-1]
    return count % 2 == p
    
if __name__ == "__main__":
    main()

Solution (Python):
N,M = (int(x) for x in input().split())
a = [0]*N  
k = []
ans = 0
for i in range(M):
  k = [int(x) for x in input().split()]
  for j in range(k[0]): 
    s = k[j+1]-1

    a[s] = a[s] | (1<<i) 

    
p = [int(x) for x in input().split()]
P = 0
for i in range(M):
  P |= p[i] << i





for s in range(1<<N):
  t = 0
  for i in range(N):
    if ((s>>i) & 1):
      t ^= a[i]		
      
  if (t == P):	
    ans += 1
print(ans)

Solution (Python):
N,M = (int(x) for x in input().split())
a = [0]*N  
k = []
ans = 0
for i in range(M):
  k = [int(x) for x in input().split()]
  for j in range(k[0]): 
    s = k[j+1]-1

    a[s] = a[s] | (1<<i)

    
p = [int(x) for x in input().split()]
P = 0
for i in range(M):
  P |= p[i] << i
for s in range(1<<N):
  t = 0
  for i in range(N):
    if ((s>>i) & 1):
      t ^= a[i]
  if (t == P):
    ans += 1
print(ans)

Solution (Python):
n,m=[int(x) for x in input().rstrip().split()]
temp=[0 for i in range(m)]

ans=0
l=[]
for i in range(m):
  ks=[int(x) for x in input().rstrip().split()]
  l.append(ks)
p=[int(x) for x in input().rstrip().split()]

for i in range(2**n):
  flag=1
  for j in range(n):
    if i>>j & 1:
      for s in range(m):
        for k in range(1,l[s][0]+1):
          if (j+1)==l[s][k]:
            temp[s]+=1

  for t in range(m):
    if temp[t]%2!=p[t]:
      flag=0
      break
  
  if flag==1:
    ans+=1
  temp=[0 for ini in range(m)]

print(ans)

Solution (Python):
from itertools import product
N, M = map(int, input().split())
denkyu = []
for i in range(M):
    denkyu.append([int(j) for j in input().split()])
p = [int(i) for i in input().split()]
ls = [0, 1]
ans = 0
for x in product(ls, repeat=N):
    num = 0
    for j, denkyu_ in enumerate(denkyu):
        num_light_on = 0
        for i, s in enumerate(denkyu_):
            if i != 0 and x[s-1] == 1:
                num_light_on += 1
        if num_light_on%2 == p[j]:
            num += 1
    if num == M:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    all_on_flag = 1
    for j in range(m):
        switch = switches[j]
        cnt = 0
        for s in switch[1:]:
            if ((i >> (s-1)) & 1):
                cnt += 1
        if cnt % 2 != p[j]:
            all_on_flag = 0
            break
    if all_on_flag:
        ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
switches = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
    all_on_flag = 1
    for j in range(m):
        switch = switches[j]
        cnt = 0
        for s in switch[1:]:
            if i & (1 << (s-1)):
                cnt += 1
        if cnt % 2 != p[j]:
            all_on_flag = 0
            break
    if all_on_flag:
        ans += 1
print(ans)

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

on_off_patterns = []
for i in range(2 ** N):
    on_off = [0] * N
    for j in range(N):
        if ((i >> j) & 1):
            on_off[N-1-j] = 1
    on_off_patterns.append(on_off)
    
bulbs = []
for i in range(M):
    bulb_data = [int(i) for i in input().split()]
    k = bulb_data[0]
    switches = bulb_data[1:]
    bulbs.append([n -1 for n in switches])
    
p = [int(i) for i in input().split()]

cnt = 0
for pattern in on_off_patterns:
    bulb_on_off = [0] * M
    for b in range(len(bulbs)):
        value = 0
        for s in range(len(bulbs[b])):
            value += pattern[bulbs[b][s]]
            
        if value % 2 == p[b]:
            bulb_on_off[b] = 1
        else :
            bulb_on_off[b] = 0
    if sum(bulb_on_off) == M:
        cnt += 1
print(cnt)