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

Solution (Python):

import sys
import math
import os
import itertools
import _collections
import string

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]
    def intColsList(n):
        return [int(input()) for i in range(n)]
        
class Math():
    def gcd(a,b):
        if b == 0:
            return a
        return Math.gcd(b,a % b)
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Math.roundUp(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x
    def nearPow2(n):
        if n <= 0:
            return 0
        if n & (n - 1) == 0:
            return n
        ret = 1
        while(n > 0):
            ret <<= 1
            n >>= 1
        return ret

def main():
    N,M = cin.mapInt()
    S = [[] for i in range(N)] 
    for i in range(M):
        s = cin.mapInt()
        k = s[0]
        for j in range(k):
            a = s[j + 1] - 1
            S[a].append(i)
    ans = 0
    P = cin.mapInt()
    for i in range(1 << N):
        tmp = [0] * M
        isOK = True
        for j in range(N):
            if i >> j & 1:
                for k in S[j]:
                    tmp[k] += 1
        for j in range(M):
            if P[j] % 2 != tmp[j] % 2:
                isOK = False
        if isOK:
            ans += 1
    print(ans)
    return

if __name__ == "__main__":
    main()

Solution (Python):
N, M = map(int, input().split())
Mat = [[0 for i in range(N)] for i in range(M)]
for i in range(M):
  sw = list(map(int, input().split()))
  for j in range(1, sw[0]+1):
    Mat[i][sw[j]-1] = 1
p = list(map(int, input().split()))
pat = 2**N
cnt = 0
for i in range(pat):
  A = []
  for j in range(N):
    A.append(i%2)
    i //= 2
  B = [sum(A[i]*Mat[j][i] for i in range(N)) % 2 for j in range(M)]
  if B == p:
    cnt += 1
print(cnt)

Solution (Python):
n,m = map(int,input().split())
l = [list(map(int,input().split()))[1:]for i in range(m)]
p = list(map(int,input().split()))
form = "0"+str(n)+"b"
ans = 0
for i in range(2**n):
    ptn = format(i,form)
    light = True
    for j in range(m):
        s = sum(int(ptn[k-1])for k in l[j])
        if s%2 != p[j]:
            light = False
    if light == True:
        ans += 1
print(ans)

Solution (Python):

n, m = map(int, input().split())
cnct = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))

ans = 0

for i in range(2 ** n):
    for idx, j in enumerate(cnct):
        switch_num = j[0]
        res = 0
        for k in range(1, switch_num + 1):
            if i & (1 << (j[k] - 1)):
                res += 1
        if res % 2 == p[idx]:
            continue
        else:
            break
        
    else:
        ans += 1

print(ans)

Solution (Python):
import itertools

N, M = [int(i) for i in input().split()]
KS = []
for _ in range(M):
    KS.append(tuple([int(i) for i in input().split()]))
P = tuple([int(i) for i in input().split()])

ans = 0
for t in itertools.product([0, 1], repeat=N):
    for m in range(M):
        if sum(t[x - 1] for x in KS[m][1:]) % 2 != P[m]:
            break
    else:
        ans += 1
print(ans)

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

ans = 0
for i in range(2**n):
    x = str(bin(i))[2:]
    if len(x) < n:
        x = "0" * (n - len(x)) + x
    a = 1
    for j in range(m):
        check = 0
        for k in light[j][1:]:
            if x[k-1] == "1":
                check += 1
        if check % 2 != p[j]:
            a = 0
            break
    if a:
        ans += 1
print(ans)

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

k = []
s = []
switch = list([[0 for i in range(m)]for i in range(n)])
switch_1 = [0 for i in range(n)]
cnt = 0

for i in range(1,len(p)+1):
    if p[i-1] == 1:
        cnt += 2**(m-i)
    if i == m:
        p_1 = cnt

for i in range(m):
    k.append(k_and_s[i][0:1][0])
    s.append(k_and_s[i][1:])

for i in range(len(s)):
    for j in range(len(s[i])):
        switch[s[i][j]-1][i] = 1

for i in range(len(switch)):
    cnt = 0
    for j in range(1,len(switch[i])+1):
        if switch[i][j-1] == 1:
            cnt += 2**(m-j)
        if j == m:
            switch_1[i] = cnt

ans = 0
for i in range(1<<n):
    t = 0
    for j in range(n):
        if i >> j & 1 != 0:
            t ^= switch_1[j]
    if t==p_1:
        ans +=1
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[]
  for _ in range(m):
    a=LI()
    l.append(a[1:])

  lp=LI()

  a=[]
  for i in range(1<<n):
    _a=[]
    for j in range(n):
      if i&(1<<j):
        _a.append(1)
      else:
        _a.append(0)
    a.append(_a)

  ans=0
  for x in a:
    f=True
    for i,y in enumerate(l):
      _sum=0
      for z in y:
        _sum+=x[z-1]
      if _sum%2!=lp[i]:
        f=False
        break
    if f:
      ans+=1

  return ans


print(main())

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

for i in range(2**n):
    check2 = [0]*m
    for j in range(n):
        if ((i>>j) & 1):
            for k in range(m):
                
                if j+1 in check[k]:
                    check2[k] += 1
                    
    check3 = True
    for l in range(m):
        if check2[l]%2 != p[l]:
            check3 = False
    if check3 :
        count += 1
        

print(count)

Solution (Python):

si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
snm = lambda: map(str, input().split())
nl = lambda: list(map(int, input().split()))

n,m=nm()
s=[]
o=[]
for i in range(m):
    s.append(nl())
p=nl()

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

ans=0
denkyu=0
for oo in o:
    denkyu=0
    for i in range(m):
        cnt=0
        k=s[i][0]
        for j in range(k):
            if oo[s[i][j+1]-1]==1:
                cnt+=1
        if cnt%2==p[i]:
            denkyu+=1
    if denkyu==m:ans+=1
print(ans)

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



def format(X, n):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    return out



def format0(X, n, m):
    X_dumy = X
    out = ''
    while X_dumy>0:
        out = str(X_dumy%n)+out
        X_dumy = int(X_dumy/n)
    if len(out) < m:
        out = "0" * (m - len(out)) + out
    return out

ans = 0
for i in range(2**n):
  i = format0(i,2,n)
  switch = [int(i[j]) for j in range(n)]
  on=0
  for j in range(m):
    if sum([switch[li[j][l+1]-1] for l in range(li[j][0])]) % 2 == p[j]:
      on += 1
  if on == m:
    ans += 1
print(ans)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split()))[1:] for i in range(m)]
p=list(map(int,input().split()))
form = "0" + str(n) + "b"
ans=0
for i in range(2**n):
	ptr = format(i,form)
	flg = True
	for j in range(m):
		s= sum(int(ptr[k-1]) for k in l[j])
		if s%2 != p[j]:
			flg = False
	if flg == True:
		ans+=1
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()

  l=[]
  for _ in range(m):
    a=LI()
    l.append(a[1:])

  l2=LI()

  pattern=[]
  for i in range(1<<n):
    _l=[]
    for j in range(n):
      _l.append(1 if i&(1<<j) else 0)
    pattern.append(_l)

  ans=0
  for x in pattern:
    f=True
    for i,y in enumerate(l):
      on_num=0
      for z in y:
        on_num+=x[z-1]

      if not f:
        break
      if f and l2[i]!=on_num%2:
        f=False
        break

    if f:
      ans+=1

  return ans


print(main())

Solution (Python):
n,m=map(int,input().split())
slis=[]
counter=0
for i in range(m):
	s=list(map(int,input().split()))
	s.remove(s[0])
	slis.append(s)
plis=list(map(int,input().split()))

for i in range(2**n):
	sw_st=list(format(i,"b").zfill(n))
	alis=[]
	for j in range(m):
		c=0
		for k in range(n):
			if sw_st[k]=="1" :
				if k+1 in slis[j]:
					c+=1
		alis.append(c%2)
	if alis==plis:
		counter+=1
print(counter)

Solution (Python):
import itertools

N, M = map(int, input().split())
KS = []
for _ in range(M):
    KS.append(tuple(map(int, input().split())))
P = tuple(map(int, input().split()))

ans = 0
for t in itertools.product([0, 1], repeat=N):
    for m in range(M):
        if sum(t[x - 1] for x in KS[m][1:]) % 2 != P[m]:
            break
    else:
        ans += 1

print(ans)

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

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

p=list(map(int,input().split()))
    
ans=0
for i in range(pow(2,N)):
    light=0
    for j in range(M):
        temp=0
        for kk in range(k[j]):
            a=i>>(s[j][kk]-1)
            if a&1==1:
                temp+=1
        if temp%2!=p[j]:
            break
        light+=1
    if light==M:
        ans+=1
               
print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split(" "))
    S = []
    for _ in range(M):
        tmp = list(map(int, input().split(" ")))[1:]
        binary_s = 0
        for t in tmp:
            binary_s += 2 ** (t - 1)
        S.append(binary_s)
    P = list(map(int, input().split(" ")))
    result = 0
    for i in range(2 ** N):
        for s, p in zip(S, P):
            if not bin(s & i).count("1") % 2 == p:
                break
        else:
            result += 1
    print(result)


if __name__ == '__main__':
    main()

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

ans = 0
switchState = [0]*n


def dfs(i, tukeru):
    
    if(i == n):
        sumOfTento = 0
        for denkyu in range(m):
            sumOfswitch = 0
            for switch in switches[denkyu]:
                sumOfswitch += switchState[switch-1]
            if(sumOfswitch % 2 == p[denkyu]):
                sumOfTento += 1
        
        if(sumOfTento == m):
            return 1
        else:
            return 0
    switchState[i] = tukeru
    return dfs(i+1, 0) + (dfs(i+1, 1) if i != n-1 else 0)


print(dfs(0, 0)+dfs(0, 1))

Solution (Python):
import sys
 
 
def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass
 
        if dec % 2 == p[x]:
            pass
        else:
            return 0
 
    return 1
 
 
def main():
    N, M = map(int, input().split())
 
    k = [0] * M
    s = [0] * M
    for i in range(M):
        k[i], *s[i] = map(int, input().split())
 
 
    p = list(map(int, input().split()))
 
    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)
 
    print(ans)
 
if __name__ == '__main__':
    main()

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

ans=0
for bit in range(1<<n):
  x=0
  for i in range(m):
    y=0
    for j in s[i]:
      if bit&(1<<(j-1)):
        y+=1
    if y%2==p[i]%2:
      x+=1
  if x==m:
    ans+=1

print(ans)

Solution (Python):
import itertools

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

s = [list(map(int,input().split())) for _ in range(m)]
p = list(map(int,input().split()))

li = [0,1]
ans = 0
for elm in itertools.product(li,repeat=n):
    for i in range(m):
        mm = 0
        for j in range(1,s[i][0]+1):
            if elm[s[i][j]-1]==1:
                mm += 1
        if mm%2!=p[i]:
            break
    else:
        ans += 1
        
print(ans)

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

Solution (Python):


N, M = map(int, input().split())
l_list = []
for _ in range(M):
    data = list(map(int, input().split()))[1:]
    l_list.append(sum(2**(x-1) for x in data))

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


count = 0
for sw in range(2**N):
    for l, p in zip(l_list, p_list):
        A = l & sw
        A = (0x55555555 & A) + ((0xAAAAAAAA & A)>>1)
        A = (0x33333333 & A) + ((0xCCCCCCCC & A)>>2)
        A = (0x0f0f0f0f & A) + ((0xf0f0f0f0 & A)>>4)
        A = (0x00ff00ff & A) + ((0xff00ff00 & A)>>8)
        A = (0x0000ffff & A) + ((0xffff0000 & A)>>16)
        if A % 2 != p:
            break
    else:
        count += 1
print(count)

Solution (Python):
def calculate(n,m,arr,p):
    total = 0
    for i in range(2**n):
        

        check = [False for i in range(m)]
        for indexOfBlub in range(len(arr)):
            
            onNumOfTheBlub = 0
            for indexOfSwitch in range(len(arr[indexOfBlub])):
                if i >> (arr[indexOfBlub][indexOfSwitch] - 1) & 1:
                    onNumOfTheBlub += 1

            

            if onNumOfTheBlub % 2 == p[indexOfBlub]:
                check[indexOfBlub] = True

        if all(check):
            total += 1

    return total

n = 5
m = 2

S = input()
S = S.split(" ")
n = int(S[0])
m = int(S[1])


inputArr = []


for i in range(m):
    S = input()
    inputArr.append([int(s) for s in S.split(" ")][1:])

S = input()
inputP = [int(s) for s in S.split(" ")]


res = calculate(n,m,inputArr,inputP)

print(res)

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


connected_switches = [[int(i) - 1 for i in input().split()[1:]]
                      for _ in range(M)]
ps = list(map(int, input().split()))



ans = 0

for bit in range(2 ** N):
    ok = True
    
    for i in range(M):
        
        connected_on_num = 0
        for s in connected_switches[i]:
            """
            今確認しているパターン（bit）で
            i番目の電球に繋がっているスイッチsがonとなる場合
            例: Nが4、bitが3は
            0番目: ON
            1番目: ON
            2番目: OFF
            3番目: OFF
            を想定している
            このケースで、forで回しているs（i番目の電球に繋がっているスイッチ）が
            0番目もしくは1番目のとき、connected_numが加算され2となる
            """
            if bit & (1 << s):
                """
                1 を左にsだけシフトする（10進数では2 ** s を掛けることと同じ）
                1 << 0 は 2進数で0001、10進数で1
                1 << 1 は 2進数で0010、10進数で2
                1 << 2 は 2進数で0100、10進数で4...
                bitが3のとき（2進数で0010のとき）
                bit & (1 << s) は
                0011 & (1 << s) という演算が行われる
                これがTrueとなるのは
                sが0: (1 << s) → (1 << 0) → 0001
                sが1: (1 << s) → (1 << 1) → 0010
                のときだけ
                """
                connected_on_num += 1
        if connected_on_num % 2 != ps[i]:
            ok = False
            break
    
    
    if ok:
        ans += 1

print(ans)

Solution (Python):
def is_all_switches_on(on_case):
    for i, s in enumerate(S):
        on_switch_num = 0
        for si in s:
            if on_case[si] == '1':
                on_switch_num += 1

        if on_switch_num % 2 != switches[i]:
            return False
    return True

if __name__ == '__main__':
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        k, *s = map(int, input().split())
        S.append(s)

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

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

        on_case = '0' + bin(i)[2:].zfill(N)
        if is_all_switches_on(on_case):
            ans += 1
    print(ans)

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

for j in range(2 ** N):
  ss = format(s, "010b")[10 - N:]
  m = 0
  for k in range(M):
    if sum([int(ss[i-1]) for i in Lumps[k]]) % 2 == p[k]:
      m += 1
    else:
      break
  if m == M:
    ans += 1
  s += 1
print(ans)

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

for j in range(2 ** N):
  ss = format(s, "010b")[10 - N:]
  m = 0
  for k in range(M):
    if sum([int(ss[i-1]) for i in Lumps[k]]) % 2 == p[k]:
      m += 1
    else:
      break
  if m == M:
    ans += 1
  s += 1
print(ans)

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

ans = 0
for i in range(1 << N):
    flg = True
    for j in range(M):
        cnt = 0
        for s in S[j]:
            if i & (1<<(s-1)):
                cnt += 1
        if cnt % 2 != P[j]:
            flg = False
            break

    if flg:
        ans += 1

print(ans)

Solution (Python):
from sys import stdin


def dfs(s, p, P, i):
    
    
    if len(s) == i:
        return 1 if P == p else 0
    
    
    return dfs(s, p, P, i + 1) + dfs(s, p, P ^ s[i], i + 1)


def main():
    lines = stdin.readlines()
    N, M = map(int, lines[0].split())
    sn = [[int(j) for j in i.split()[1:]] for i in lines[1:-1]]
    pn = (int(i) for i in lines[-1].split())
    
    
    s = [0] * N
    for i in range(M):
        for j in sn[i]:
            s[j - 1] |= (1 << i)
    
    
    
    
    p = 0
    for i, j in enumerate(pn):
        p |= (1 << i) if j == 1 else 0
    print(dfs(s, p, 0, 0))


main()

Solution (Python):
def examA():
    A, P = LI()
    ans = (A*3+P)//2
    print(ans)
    return

def examB():
    N = I()
    SP = [[]for _ in range(N)]
    for i in range(N):
        SP[i] = LSI()
        SP[i][1] = int(SP[i][1])
        SP[i].append(i)

    SP = sorted(SP,key = lambda x:x[1], reverse = True)
    SP = sorted(SP,key = lambda x:x[0])

    for v in SP:
        print(v[2]+1)
    return

def examC():
    N, M = LI()
    S = [LI() for _ in range(M)]
    P = LI()
    ans = 0
    loop = 2**N
    for i in range(loop):
        flag = True
        d = defaultdict(bool)
        for j in range(N):
            if i&(1<<j)==(1<<j):
                d[j+1] = True
        for l,j in enumerate(S):
            cur = 0
            for k in range(1,j[0]+1):
                if d[j[k]]:
                    cur +=1
            if cur%2!=P[l]:

                flag = False
                break
        if flag:
            ans +=1
    print(ans)

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

Solution (Python):
from itertools import product
n,m=map(int,input().split())
KS=[list(map(int,input().split())) for _ in range(m)]
P=list(map(int,input().split()))
kumiawase = list(product([0,1], repeat=n))
cnt=0
flag=0
for i in range(2**n):
    flag=0
    junban=kumiawase[i]
    for j in range(m):
        joutai=0      
        for k in range(KS[j][0]):
            joutai+=junban[KS[j][k+1]-1]
        if joutai%2==P[j]:
            flag+=0
        else:
            flag=1
    if flag==0:
        cnt+=1
print(cnt)

Solution (Python):
n,m = map(int,input().split())
b = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
c = 0
for i in range(1 << n):
    a = [0]*n
    for j in range(n):
        if ((i >> j) & 1) == 1:
            a[j] = 1
    for k in range(m):
        if sum(a[l-1] for l in b[k][1:])%2 == p[k]:
            continue
        else:
            break
    else:
        c += 1
print(c)

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

answer = 0
for i in range(2 ** N):
  cnt = 0
  for j in range(M):
    tmp = 0
    for s in S[j]:
      if (i >> (s - 1)) & 1:
        tmp = 1 - tmp
    if tmp % 2 == P[j]:
      cnt += 1
  if cnt == M:
    answer += 1
    
print(answer)

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(2 ** N):
    switch_list = [0] * N
    flag = True     
    for j in range(N):
        if i & (1 << j):    
            switch_list[j] = 1
    for k in range(M):  
        on_swtich = 0
        for s in range(ks[k][0]):   
            if switch_list[ks[k][s+1] - 1] == 1:
                on_swtich += 1
        if on_swtich % 2 == p[k]:
            pass
        else:
            flag = False
            break
    if flag:
        ans += 1

print(ans)

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

Solution (Python):
n, m = map(int, input().split())
ks = [list(map(int, input().split())) for i in range(m)]
p = list(map(int, input().split()))
ans = 0
for i in range(2**n):
  switch = [0]*n
  j = 0
  while j < n:
    if (i>>j) & 1:
      switch[j] = 1
    j += 1
  light = [0]*m
  for l in range(m):
    for x in range(ks[l][0]):
      if switch[ks[l][x+1]-1] == 1:
        light[l] += 1
  on = 0
  for l in range(m):
    if light[l]%2 != p[l]:
      continue
    on += 1
  if on == m:
    ans += 1

print(ans)

Solution (Python):
import sys

def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass

        if dec % 2 == p[x]:
            pass
        else:
            return 0

    return 1


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

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

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


    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def check(bits, M, k, s, p):
    for x in range(M):
        dec = 0
        for K in range(k[x]):
            if bits >> (s[x][K] - 1) & 1:
                dec += 1
            else:
                pass

        if dec % 2 == p[x]:
            pass
        else:
            return 0

    return 1


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

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


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

    ans = 0
    for bits in range(2 ** N):
        ans += check(bits, M, k, s, p)

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import itertools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m = na()
s = []
for _ in range(m):
    s.append(na()[1:])
p = na()
ans = 0
for switch in itertools.product([0,1], repeat=n):
    flag = True
    for si, pi in zip(s, p):
        c = sum(switch[i-1] for i in si)
        if c % 2 != pi:
            flag = False
            break
    if flag == True:
        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
import numpy as np

for x in range(2**N):
  bin_str = format(x, '0{0}b'.format(N))
  X=np.array(list(map(int,list(bin_str))))
  flg=True
  for i in range(M):
    if sum(X[np.array(ks[i][1:])-1])%2 != p[i]:
      flg=False
      break
  if flg:
    ans+=1
print(ans)

Solution (Python):
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
p=list(map(int,input().split()))
res=0
for i in range(2**n):
    b=list(str(bin(i))[2:].zfill(n))
    
    my=True
    for j in range(m):
        pre=0
        for k in range(a[j][0]):
            
            pre+=int(b[a[j][k+1]-1])
        if p[j]==0:
            if pre%2!=0:
                my=False
        else:
            if pre%2!=1:
                my=False
        
    
    if my:
        
        res+=1
print(res)

Solution (Python):
N,M = map(int,input().split())
lamp_list = []
for j in range(M):
  lamp_list.append([i-1 for i in map(int,input().split())])
  lamp_list[j].pop(0)
mod_list = [i for i in map(int,input().split())]

ans = 0

for i in range(2**N):
  sum_list = [0 for i in range(M)] 
  for j in range(N):
    if ((i>>j)&1):
      for k in range(M):
        if j in lamp_list[k]:
          sum_list[k] += 1
  ok = 1
  for k in range(M):
    if sum_list[k]%2 != mod_list[k]:
      ok = 0
  if ok:
    ans += 1
    
print(ans)

Solution (Python):
def cntBit(n):
    cnt = 0
    while n > 0:
        cnt += (n & 1)
        n >>= 1
    return cnt


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

switch = [list(map(int, input().split())) for _ in range(M)]
B = []
for K, *S in switch:
    b = 0
    for k in range(K):
        b += (1 << (S[k] - 1))
    B.append(b)
P = list(map(int, input().split()))

ans = 0
for i in range(2 ** N):
    on = True
    B1 = list(map(lambda x: x & i, B))
    B2 = list(map(cntBit, B1))
    B3 = list(map(lambda x: x % 2, B2))

    if B3 == P:
        ans += 1

print(ans)

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

switch = [list(map(int, input().split())) for _ in range(M)]
B = []
for K, *S in switch:
    b = 0
    for k in range(K):
        b += (1 << (S[k] - 1))
    B.append(b)

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

ans = 0
for i in range(2 ** N):
    on = True
    for j, b in enumerate(B):
        cnt = 0
        state = b & i
        while state > 0:
            cnt += state & 1
            state >>= 1
        on &= (cnt % 2 == P[j])
    ans += on

print(ans)

Solution (Python):

N, M = map(int, input().split())
S = []
for i in range(M):
    tmp = list(map(int, input().split()))
    S.append(tmp[1:])
P = list(map(int, input().split()))
ans = 0

for bit in range(2**N):
    l = []
    for j in range(N):
        if bit >> j & 1 == 1:
            l.append(1)
        else:
            l.append(0)
    flag = True
    for j in range(M):
        t = S[j]
        cnt = 0
        for k in range(len(S[j])):
            if l[t[k]-1] == 1:
                cnt += 1
            
            
        if cnt % 2 != P[j]:
            flag = False
    if flag:
        
        ans += 1
print(ans)

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


connected_switches = [[int(i) - 1 for i in input().split()[1:]]
                      for _ in range(M)]
ps = list(map(int, input().split()))



ans = 0

for bit in range(2 ** N):
    ok = True
    
    for i in range(M):
        
        connected_on_num = 0
        for s in connected_switches[i]:
            
            
            
            
            
            
            
            
            
            if bit & (1 << s):
                connected_on_num += 1
        if connected_on_num % 2 != ps[i]:
            ok = False
            break
    
    
    if ok:
        ans += 1

print(ans)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    bulbs = []
    for _ in range(M):
        b = tuple(map(int, input().split()))
        bulbs.append(b[1:])

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

    ans = 0
    for switch in range(2**N):
        check = [0] * M
        for i, bulb in enumerate(bulbs):
            cnt = 0
            for b in bulb:
                if switch >> (b - 1) & 1:
                    cnt += 1

            if cnt % 2 == P[i]:
                check[i] = True
            else:
                check[i] = False

        if all(check):
            ans += 1

    return ans


if __name__ == '__main__':
    print(main())