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())
swich = [set() for i in range(N)]
ans = 0
b = 0
for i in range(M):
  S = list(map(int, input().split()))
  for j in range(1, len(S)):
    swich[S[j] - 1].add(i)
P = list(map(int, input().split()))
for i in range(2**N):
  light = [0 for i in range(M)]
  for j in range(N):
    if i >> j & 1 == 1:
      for x in swich[j]:
        light[x] += 1
  if all(light[i] % 2 == P[i] for i in range(M)):
    ans += 1
print(ans)

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

for i in range(M):
    k, *s = map(int, input().split())
    
    memo[i] = s

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

ans = 0
for i in range(2**N):
    tmp = 0
    for idx, light in enumerate(memo):
        on_switches = 0
        for j in range(N):
            if i >> j & 1:
                if j+1 in light:
                    on_switches += 1
        if on_switches % 2 == P[idx]:
            tmp += 1
    if tmp == M:
        ans += 1

print(ans)

Solution (Python):

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


connect = []

for i in range(m):
    condi = list(map(int, input().split()))[1:]
    connect.append(condi)
        
    
state = list(itertools.product([0,1], repeat = n))

ans = input().split()

def abc128c(n, m, state, condi, ans):
    pika = [0 for i in range(m)]
    for i in range(m):
        
        on_off = 0
        for j in condi[i]:
            on_off += state[j-1]
        if on_off % 2 == ans[i]:
            pika[i] = 1
    output = 0
    
    if pika == [1 for i in range(m)]:
        output =1
    
    
    return output



count = 0
for a in state:
    count += abc128c(n, m, a, connect, list(map(int, ans)))
    
print(count)

Solution (Python):
from itertools import product
from operator import itemgetter

N, M = map(int, input().split())
lights = list(tuple(map(int, input().split())) for _ in range(M))
cons = list(map(int, input().split()))

ans = 0
for switch in product(range(2), repeat=N):
    reminders = []
    for idx, light in enumerate(lights):
        f = itemgetter(*map(lambda x: x - 1, light[1:]))
        if isinstance(f(switch), int):
            s = f(switch)
        else:
            s = sum(f(switch))
        reminders.append(s % 2)
    if cons == reminders:
        ans += 1
print(ans)

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

switch_state_list=[]
ans = 0

for _ in range(M):
    temp = list(map(lambda x:int(x)-1, input().split()))
    k.append(temp[0]+1)
    s.append(temp[1:])

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


def check_denqu(switch_state):
    denqu_state=[0]*M

    for i in range(M):
        on_num = 0
        for index in s[i]:
            on_num += switch_state[index]
        if on_num % 2 == p[i]:
            denqu_state[i]=1
        else:
            denqu_state[i]=0
    
    if all(denqu_state):
        return 1
    else:
        return 0


def dfs(i, m):
    global ans

    switch_state_list.append(m)
    if i == N-1:
        ans += check_denqu(switch_state_list)
        switch_state_list.pop()
        return 
   
    dfs(i+1, 0)
    dfs(i+1, 1)

    switch_state_list.pop()


dfs(0,0)
dfs(0,1)

print(ans)

Solution (Python):
def main():
  n, m = map(int, input().split())
  g = [[-1]*n for _ in range(m)]
  for i in range(m):
    s = list(map(int, input().split()))
    for j in s[1:]:
      g[i][j-1] = 1
  p = list(map(int, input().split()))

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

if __name__ == '__main__':
  main()

Solution (Python):
N,M=map(int,input().split())
s=[list(map(int,input().split()))[1:] for m in range(M)]
p=list(map(int,input().split()))
count=0
for i in range(1<<N):
    for m in range(M):
        switch=0
        for j in range(N):
            if (i>>j)&1 and j+1 in s[m]:
                switch+=1
        if switch%2!=p[m]:
            break
    else:
        count+=1
print(count)

Solution (Python):
n,m = (int(x) for x in input().split())
swi = []
for i in range(m):
  l = [int(x) for x in input().split()]
  t = 0
  for i in range(1,len(l)):
    t += 1 << (l[i]-1)
  swi.append(t)
ppp = [int(x) for x in input().split()]

ans = 0
for i in range(1 << n):
  for s, p in zip(swi,ppp):
    t = i & s
    c = bin(t).count("1") % 2
    if c != p:
      break
  else:
    ans += 1
print(ans)

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

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

p = 0
_p = list(map(int, input().split()))
for i in range(m):
    p |= _p[i] << i

ans = 0
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 = map(int, input().split())
a = [0] * m

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

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

count = 0
for i in range(2**n):
    flg = True
    for j in range(m):
        if bin(i & a[j]).count("1") % 2 != p[j]:
            flg = False
            break
    if flg:
        count += 1

print(count)

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

for i in range(m):
    x = list(map(int, input().split()))
    for j in range(x[0]):
        s[i] += 2**(x[1+j] - 1)

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

count = 0
for i in range(2**n):
    flg = True
    for j in range(m):
        if bin(i & s[j]).count("1") % 2 != p[j]:
            flg = False
            break
    if flg:
        count += 1

print(count)

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

k = []
s = []

for _ in range(M):
    tmp = tuple(map(int, input().split()))
    k.append(tmp[0])
    s.append(set(tmp[1:tmp[0] + 1]))

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



ans = 0

for i in range(2 ** N):
    
    light_on = 0

    
    for j in range(M):
        switch_on = 0

        for k in range(N):
            
            if (i >> k) & 1:
                
                if k + 1 in s[j]:
                    switch_on += 1

        
        if switch_on % 2 == p[j]:
            light_on += 1

    
    if light_on == M:
        
        ans += 1

print(ans)

Solution (Python):


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

cnt=0
for bit in range(2**N):
    c=1
    for i in range(M):
        ons=0
        for j in range(ks[i][0]):
            k=ks[i][j+1]-1
            if (bit>>k & 1):
                ons+=1
        if ons % 2 != ps[i]:
            c*=0
            break
    if c==1:
        cnt+=1
print(cnt)

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
temp = [0]*N
for i in range(2**N):
    
    for j in range(N):
        if((i >> j) & 1):
            temp[j] = 1
    

    for k in range(M):
        count = 0
        for l in range(1, len(S[k])):
            if temp[S[k][l] - 1] == 1:
                count += 1
        if count % 2 != p[k]:
            break
    else:
        ans += 1
    temp = [0]*N

print(ans)

Solution (Python):
import itertools

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


ans = 0
for bit in itertools.product([0, 1], repeat=N):
    for d, p in zip(data, P):
        cnt = 0
        for i in d[1:]:
            if bit[i - 1] == 1:
                cnt += 1
        if cnt % 2 != p:
            break
    else:
        ans += 1

print(ans)

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

s = [0] * m

for i in range(m):
    k, *li = map(int, input().split())
    for j in range(k):
        s[i] += 2**(li[j]-1)

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


ans = 0

for i in range(2**n):
    tmp = True
    for j in range(m):
        if bin(i & s[j]).count("1") % 2 != p[j]:
            tmp = False
            break

    if tmp:
        ans += 1

print(ans)

Solution (Python):
N,M=list(map(int,input().split()))
a=""
sw=[]
pattern=[]
def bit(i,turn):
    if i==N:
        pattern.append(list(turn))
    else:
        bit(i+1,turn+"0")
        bit(i+1,turn+"1")
for i in range(M):
    k=list(map(int,input().split()))
    sw.append(k)
hantei=list(map(int,input().split()))
bit(0,a)
count=0
ans=0
for i in pattern:
    sw_list=[0]*(N+1)
    for j in range(M):
        k=sw[j]
        for l in k[1:]:
            if i[l-1]=="1":
                sw_list[j]+=1
    for m in range(M):
        if sw_list[m]%2!=hantei[m]:break
    else:ans+=1
print(ans)

Solution (Python):
N,M=list(map(int,input().split()))
a=""
sw=[]
pattern=[]
def bit(i,turn):
    if i==N:
        pattern.append(list(turn))
    else:
        bit(i+1,turn+"0")
        bit(i+1,turn+"1")
for i in range(M):
    k=list(map(int,input().split()))
    sw.append(k)
hantei=list(map(int,input().split()))
bit(0,a)
count=0
ans=0
for i in pattern:
    sw_list=[0]*(N+1)
    for j in range(M):
        k=sw[j]
        for l in k[1:]:
            if i[l-1]=="1":
                sw_list[j]+=1
    for m in range(M):
        if sw_list[m]%2!=hantei[m]:break
    else:ans+=1
print(ans)

Solution (Python):
n, m = map(int, input().split())
g = [[-1]*n for _ in range(m)]
for i in range(m):
  s = list(map(int, input().split()))
  s.pop(0)
  for j in s:
    g[i][j-1] = 1
p = list(map(int, 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
  
  flag = True
  for j in range(m):
    cnt = 0
    for k in range(n):
      if g[j][k] == switch[k]:
        cnt += 1
    if cnt % 2 != p[j]:
      flag = False
  if flag:
    ans += 1

print(ans)

Solution (Python):
n, m = map(int, input().split())
g = [[-1]*n for _ in range(m)]
for i in range(m):
  s = list(map(int, input().split()))
  s.pop(0)
  for j in s:
    g[i][j-1] = 1
p = list(map(int, 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
  
  flag = True
  for j in range(m):
    cnt = 0
    for k in range(n):
      if g[j][k] == switch[k]:
        cnt += 1
    if cnt % 2 != p[j]:
      flag = False
  if flag:
    ans += 1

print(ans)

Solution (Python):
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    state = np.zeros((m,n),dtype=int)
    for i in range(m):
        ks = list(map(int,ipt().split()))
        for j in ks[1::]:
            state[i][j-1] = 1
    p = [int(i) for i in ipt().split()]
    ans = 0
    fm = "0"+str(n)+"b"
    for i in range(2**n):
        li = np.array(list(map(int,format(i,fm))))
        for i,si in enumerate(state):
            if not np.count_nonzero(li&si)%2 == p[i]:
                break
            if i == m-1:
                ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import itertools
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 item in itertools.product([0, 1], repeat=n):
    for i in range(m):
        if sum([item[j-1] for j in s[i]]) % 2 != p[i]:
            break
    else:
        ans += 1
print(ans)

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

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

ans = 0

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

print(ans)

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

for i in range(2 ** N):
    flg = True
    for j, row in enumerate(array):
        count = 0
        for k in row[1:]:
            if i & (1 << (k - 1)):
                count += 1
        if not p[j] % 2 == count % 2:
            flg = False
            break
    if flg:
        ans += 1
print(ans)

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

for i in range(2 ** n):
    x = 0 
    y = [[] for j in range(m)]
    for j in range(n):
        if ((i >> j) & 1): 
            for k in range(m):
                if j+1 in li[k]:
                    y[k].append(j+1)
    for j in range(m):
        if len(y[j]) %2 == p[j]:
            x += 1                   
    if x == m:
        ans += 1

print(ans)

Solution (Python):
import sys
from itertools import product

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    k = [None] * M
    s = [None] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
    p = list(map(int, input().split()))

    ans = 0
    for comb in product(range(2), repeat=N):
        are_on = True
        for i in range(M):
            n_on = 0
            for ss in s[i]:
                n_on += 1 if comb[ss - 1] == 1 else 0
            if n_on % 2 != p[i]:
                are_on = False
        ans += 1 if are_on else 0

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def get_subsets(fullset):
  listrep = list(fullset)
  subsets = []
  for i in range(2**len(listrep)):
    subset = []
    for k in range(len(listrep)):            
      if i & 1<<k:
        subset.append(listrep[k])
    subsets.append(subset)        
  return subsets

n, m = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(m)]
ps = list(map(int, input().split()))

ans = 0
subsets = get_subsets(set(range(1, n+1)))
for ss in subsets:
    ss = set(ss)
    b = False
    for idx in range(m):
        pat = set(mat[idx][1:])
        if len(pat&ss)%2 != ps[idx]:
            b = True
            break
    if not b:
       ans += 1
print(ans)

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

switch_list_all=[None]*n
for i in range(n):
    switch_list=[0]*m
    switch_list_all[i]=switch_list

for i in range(m):
    lst=list(map(int,input().split()))
    for j in range(len(lst)-1):
        switch_list_all[lst[j+1]-1][i]+=1
        

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

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


for i in range(len(a_list)):
    a=a_list[i]
    point=[0]*m
    c=0
    for z in range(m):
        point[z]+=p[z]
    for j in range(n):
        s_list=switch_list_all[j]
        if a[j]==1:
            for x in range(m):
                point[x]+=s_list[x]
    for y in range(m):
        if point[y]%2==0:
            c+=1
    if c==m:
        count+=1

print(count)

Solution (Python):
import numpy as np
import itertools

N, M = map(int, input().split())
L = []
S = [np.array([0 for _ in range(M)]) for _ in range(N)]

for _ in range(M):
  l = list(map(int, input().split()))
  L.append(l)

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

l = 0
for s in L:
  l += 1
  for i in range(s[0]):
    S[s[1+i]-1][l-1] += 1

for T in itertools.product([1,0], repeat = N):
  Flag = True
  ans = np.zeros(M)
  for i in range(N):
    if T[i] == 1:
      ans += S[i]
  for j in range(M):
    if ans[j] % 2 != P[j]:
      Flag = False
  if Flag:
    cnt += 1

print(cnt)

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


def dfs(n, sw):
  if n > 0:
    return dfs(n-1, sw + [0]) + dfs(n-1, sw + [1])
  else:
    answer = 1
    for m in range(M):
      count = 0
      for k in range(K[m]):
        count += sw[S[m][k]-1]
      if count % 2 != P[m]:
        answer = 0
        break
    return answer
        
print(dfs(N, []))

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

res = 0
for i in range(2**N):
    switch = [0]*N
    for j in range(N):
        if (i >> j) & 1:
            switch[j] = 1
    light_cnt = 0 
    for j in range(M): 
        cnt = 0 
        for k in range(1,switch_inf[j][0]+1):
            if switch[switch_inf[j][k]-1]:
                cnt += 1
        if cnt%2 == p[j]:
            light_cnt += 1
    if light_cnt == M:
        res += 1
print(res)

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

res=0
perms=[]
for i in range(2**n):
    list2 = []
    for j in range(n):
        if (i >> j) &1 == 1:
            list2.append(1)
        else:
            list2.append(0)
    perms.append(list2)
    ons=0
    for idx,p in enumerate(ps):
        cnt=0
        for k in ks[idx]:
            if list2[k-1]==1:
                cnt+=1
        if cnt%2==p:
            ons+=1
    if ons==m:
        res+=1
print(res)

Solution (Python):
n,m = map(int,input().split())
s = [0]*n
for i in range(m):
    k = list(map(int,input().split()))
    for j in range(1,k[0]+1):
        s[k[j]-1] |= 1<<i
p=0
k = list(map(int,input().split()))
for i in range(m):
    p |= k[i]<<i
ans = 0
for i in range(1<<n):
    t = 0
    for j in range(n):
        if i>>j&1: t^=s[j]
    if t==p: ans+=1
print(ans)

Solution (Python):

N, M = map(int, input().split())
connect_nums = []
data = []
for i in range(M):
  tmp = list(map(int, input().split()))
  connect_nums.append(tmp.pop(0))
  data.append(tmp)
switch_conditions = list(map(int, input().split()))


ans = 0
for i in range(2**N):
  on_switches = []
  for j in range(N):
    if ((i >> j) & 1):
      on_switches.insert(0, 1)
    else:
      on_switches.insert(0, 0)
      
  ansflag = True
  
  for l in range(M):
    oncnt = 0
    for ss in data[l]:
      if on_switches[ss-1] == 1:
        oncnt += 1
    if oncnt % 2 != switch_conditions[l]:
      ansflag = False
      break
  
  if ansflag:
    ans += 1
    

print(ans)


"""
print(N, M)
print(connect_nums, switch_conditions)
print(data)
"""

Solution (Python):

"""
Created on Sun May 31 10:46:22 2020

@author: NEC-PCuser
"""

N, M = map(int, input().split())
s = []
switch = [0] * N

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

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

count = 0;
for i in range(0, 2**N):
    switch = [0] * N
    for j in range(0, N):
        if ((i >> j) & 1):
            switch[j] = 1
    k = 0
    for p_split in p:
        t = 0
        for s_split in s[k]: 
            if (switch[s_split - 1]):
                t += 1
        if (t % 2 != p_split):
            break
        else:
            k += 1
    else:
        count += 1

print(count)

Solution (Python):
def check(sw, p, list):
    count = 0
    res = 0
    
    for i in range(len(sw)):
        count = 0
        for j in range(sw[i][0]):
            
            if(sw[i][j + 1] in list):
                count += 1
        if count % 2 == p[i]:
            res += 1
    
    return res == len(sw)

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

for i in range(m):
    sw.append(list(map(int,input().split())))
    
    
p = list(map(int,input().split()))
res = 0


for i in range(2**n):
    list = []
    for j in range(n):
        if(i >> j) & 1 == 1:
            list.append(j+1)
    if(check(sw,p,list)):
        res += 1
print(res)

Solution (Python):
N, M = map(int, input().split())
slist = []
for _ in range(M):
    k, *s = list(map(int, input().split()))
    slist.append(set(s))
plist = list(map(int, input().split()))
ans = 0
for i in range(2**N):
    on = set()
    pika = 0
    for j in range(N):
        if ((i >> j) & 1):
            on.add(j+1)
    for lamp_num in range(M):
        if len(slist[lamp_num]&on)%2 == plist[lamp_num]:
            pika += 1
    if pika == M:
        ans += 1
print(ans)

Solution (Python):
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

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


ans = 0
for switch in list(itertools.product([0, 1], repeat=N)):
    ok = 0
    for denkyu in range(M):
        tmp = 0
        for i in s[denkyu][1:]:
            tmp += switch[i-1]
        if(tmp % 2 == p[denkyu]):
            ok += 1
    if (ok == M):
        ans += 1

print(ans)

Solution (Python):
from itertools import product
n, m = map(int, input().split())
s = [list(map(lambda x: int(x) - 1, input().split()[1:])) for _ in range(m)]
p = list(map(int, input().split()))
print(sum(all(sum(b[ki] for ki in s[i]) % 2 == p[i] for i in range(m)) for b in product((True, False), repeat=n)))

Solution (Python):

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


import itertools
switch = list(itertools.product([0,1],repeat=n))
cnt = 0

for i in switch:
    gokei = 0
    flg = True
    for j in range(m):
        gokei = 0
        for k in range(1,len(denkyu[j])):
            gokei += i[denkyu[j][k]-1] 
            
        if gokei % 2 != p[j]:
            flg = False
            break
            
    if flg:
        cnt += 1
        
print(cnt)

Solution (Python):
n_switch, n_lamp = map(int,input().split())
lamp_switch_count = [0] * n_lamp
lamp_switch = [0] * n_lamp

for i in range(n_lamp):
    ls = list(map(int, input().split()))
    lamp_switch_count[i] = ls[0]
    ls_switch = ls[1:]
    for j in range(len(ls_switch)):
        ls_switch[j] -= 1
    lamp_switch[i] = ls_switch

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

ans = 0
for pattern in range(2**n_switch):
    all_on = True
    switch_on_ls = [0] * n_switch 
    for i_switch in range(n_switch):
        if (pattern >> i_switch) & 1:
            switch_on_ls[i_switch] = 1
    for i_lamp in range(n_lamp):
        num_target = lamp_switch_count[i_lamp]
        onswitch_num = 0
        for i in range(num_target):
            ind_of_target_switch = lamp_switch[i_lamp][i]
            if switch_on_ls[ind_of_target_switch]:
                onswitch_num += 1
        if onswitch_num % 2 != mod_ls[i_lamp]:
            all_on = False
    if all_on:
        ans += 1
print(ans)

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

cnt=0

for i in range(2**N):
    for k in range(M):
        tmp=0
        for j in range(N):
            if ((i >> j) & 1) and j+1 in s[k]:
                tmp+=1
        if tmp%2!=p[k]:
            break
    else:
        cnt+=1
print(cnt)

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):
    ptn = bin(i)[2:].rjust(N, "0")  
    light = True  
    for j in range(M):
        tmp = 0  
        for n in range(1, s[j][0] + 1):
            if ptn[s[j][n] - 1] == "1":
                tmp += 1
        if tmp % 2 != p[j] % 2:
            light = False
    if light:
        ans += 1

print(ans)

Solution (Python):
def AreAllTheLightsOn(SwitchPattern,M,LineVolume,Destinations,p):
    
    Light=0
    for m in range(M):
        OnSwitch=0
        for l in range(LineVolume[m]):
            a=Destinations[m][l]-1
            if SwitchPattern[a]==1:
                OnSwitch += 1
            else:
                pass
        if OnSwitch%2==p[m]:
            Light+=1
    
    if Light==M:
        return True


N,M=map(int,input().split())
K=[]
for _a in range (M):
    arr=list(map(int,input().split()))
    K.append(arr)
LineVolume=[] 
Destinations=[] 
for _b in range (M):
    LineVolume.append(K[_b][0])
    Destinations.append(K[_b][1:])
p=list(map(int,input().split()))




LightOnPattern=0

for Pattern in range (2**N):
    SwitchPattern=[]
    for ONOFF in range(N):
        if(Pattern>>ONOFF)&1==1:
            SwitchPattern.append(1)
        else:
            SwitchPattern.append(0)
    
    if AreAllTheLightsOn(SwitchPattern,M,LineVolume,Destinations,p)==True:
        LightOnPattern += 1

print(LightOnPattern)

Solution (Python):

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


ans = 0
for i in range(1 << n):  
    switches = [0] * n  
    flag = True
    for j in range(n):  
        if (i >> j) & 1:  
            switches[j] = 1
    for k in range(m):  
        cnt = 0  
        for t in range(len(s[k])):  
            if switches[s[k][t]] == 1:
                cnt += 1
        if cnt % 2 != p[k]:  
            flag = False
            break  
    if flag:  
        ans += 1


print(ans)

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

ary = []
for i in range(m):
	x = list(map(int, input().split()))
	x.pop(0)
	ary.append(x)

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

cnt = 0
for i in range(2**n):
	den = [0 for ii in range(n)]
	for j in range(n):
		if (i>>j) & 1:
			den[j] += 1
	flg = False
	for j in range(m):
		c = 0
		d = [0 for i in range(n)]
		for k in ary[j]:
			if den[k-1] == 1:
				d[k-1] = 1
		for kk in d:
			if kk == 1:
				c += 1
		'''
		for k in ary[j]:
			if den[k-1] ==1:
				c += 1
		'''
		if c%2 == p[j]%2:
			continue
		else:
			flg = True
			break
	if flg == False:
		cnt += 1
print (cnt)

Solution (Python):
import sys
from collections import deque
import copy
def main():
    N, M = map(int, input().split())
    s = [[] for i in range(M)]
    for i in range(M):
        lines = [int(k) for k in input().split()]
        for j in range(len(lines)):
            if j == 0:
                continue
            s[i].append(lines[j] - 1)
    p = [int(i) for i in input().split()]
    ans = 0
    for i in range(1 << N):
        switchs = [0] * N
        flag = True
        for j in range(N):
            if (i >> j) & 1:
                switchs[j] = 1
        for k in range(M):
            count = 0
            for t in range(len(s[k])):
                if switchs[s[k][t]] == 1:
                    count += 1
            if count % 2 != p[k]:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

ans = 0
for i in range(2**n):
  for x,y in zip(s, p):
    flag = False
    for a in x:
      if i & 1 << (a-1):
        flag = not flag
    if int(flag) != y:
      break
  else:
    ans += 1
print(ans)

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

k=[]
s=[]
for i in range(m):
    templist=[int(x)-1 for x in input().split()]
    k.append(templist[0]+1)
    s.append(templist[1:])

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

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

ans=0
for x in b:
    cnt=0
    for i in range(m):
        temp=0
        for j in range(len(s[i])):
            temp+=x[s[i][j]]
        if temp%2 != p[i]:
            continue
        else:
            cnt+=1
            if cnt==m:
                ans+=1
print(ans)

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

k=[]
s=[]
for i in range(m):
    templist=[int(x)-1 for x in input().split()]
    k.append(templist[0]+1)
    s.append(templist[1:])

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

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

ans=0
for x in b:
    cnt=0
    for i in range(m):
        temp=0
        for j in range(len(s[i])):
            temp+=x[s[i][j]]
        if temp%2 != p[i]:
            continue
        else:
            cnt+=1
            if cnt==m:
                ans+=1
print(ans)

Solution (Python):

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

ans = 0

lis = [ [] for i in range(N) ]

for i in range(M):

    tmp = list(map(int,input().split()))
    tmp = tmp[1:]

    for j in tmp:
        lis[j-1].append(i)

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

for i in range(2**N):

    now = [0] * M

    for j in range(N):
        if i & (2**j) > 0:
            for k in lis[j]:
                now[k] += 1

    flag = True
    for i in range(M):
        if now[i] % 2 != p[i]:
            flag = False
            break
    if flag:
        ans += 1

print (ans)

Solution (Python):
n,m=map(int,input().split())
ks=[]
for _ in range(m):
	rr=list(map(int,input().split()))
	ks.append(rr)
p=list(map(int,input().split()))
def two(x):
	return "0"*(n-len(bin(x)[2:]))+bin(x)[2:]
ans=0
for i in range(2**n):
	r=two(i)
	f=1
	for j in range(m):
		cnt=0
		for k in range(ks[j][0]):
			if r[ks[j][k+1]-1]=="1":
				cnt+=1
		if cnt%2!=p[j]:
			f=0
			break
	ans+=f
print(ans)