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.

Examples

Input

2 2
2 1 2
1 2
0 1


Output

1


Input

2 3
2 1 2
1 1
1 2
0 0 1


Output

0


Input

5 2
3 1 2 5
2 2 3
1 0


Output

8
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int N;

	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			N = s.nextInt();
			final int M = s.nextInt();

			List<BitSet> sw = new ArrayList<BitSet>((int) Math.pow(2, N));
			addSw(0, new BitSet(N), sw);

			List<BitSet> ri = new ArrayList<BitSet>((int) Math.pow(2, M));
			for (int i = 0; i < M; i++) {
				final int k = s.nextInt();
				BitSet bs = new BitSet(N);
				for (int j = 0; j < k; j++) {
					bs.set(s.nextInt() - 1, true);
				}
				ri.add(bs);
			}

			for (int i = 0; i < M; i++) {
				final int p = s.nextInt();
				List<BitSet> next = new ArrayList<BitSet>(sw.size());
				for (BitSet bs : sw) {
					BitSet w = (BitSet) bs.clone();
					w.and(ri.get(i));
					if (w.cardinality() % 2 == p) {
						next.add(bs);
					}
				}
				sw = next;
				if (next.size() == 0) {
					break;
				}
			}
			System.out.println(sw.size());
		}
	}

	static void addSw(int n, BitSet bs, List<BitSet> sw) {
		if (n == N) {
			sw.add((BitSet) bs.clone());
			return;
		}

		bs.set(n, true);
		addSw(n + 1, bs, sw);
		bs.set(n, false);
		addSw(n + 1, bs, sw);
	}
}
