У нас є \(N\) перемикачів зі станом «увімкнено» і «вимкнено», а також \(M\) лампочок.

Перемикачі пронумеровані від 1 до \(N\), а лампочки — від 1 до \(M\).

Лампочка \(i\) підключена до перемикачів \(k_i\) : перемикач \(s_{i1}, s_{i2}, ... s_{ik_i}\). Вона світиться, коли кількість перемикачів, які «ввімкнено» серед цих перемикачів, відповідає \(p_i\) по модулю 2.

Скільки комбінацій станів «увімкнено» та «вимкнено» перемикачів запалюють усі лампочки?

Формат вхідних даних

Перший рядок вхідного потоку містить цілі числа \(N,M\) (\(1 \le N,M \le 10\)).

Наступні \(M\) рядків містять \(k_i\), \(s_{i1}, s_{i2}, ... s_{ik_i}\) (\(1 \le k_i \le N\), \(1 \le s_{ij} \le N\), \(s_{ia} \neq s_{ib}(a \neq b)\))

Останній рядок містить \(p_1, p_2, ... ,p_M\) (\(p_i=0\) або \(p_i=1\)).

Формат вихідних даних

У вихідний потік виведіть шукану кількість комбінацій.

Примітка

До прикладу 1:

• Лампочка 1 горить, коли є парна кількість перемикачів, які «увімкнені»: перемикач 1 і 2.
• Лампочка 2 горить, коли є непарна кількість перемикачів, які «увімкнені» з наступного: перемикач 2.

Є чотири можливі комбінації станів (перемикач 1, перемикач 2): (увімкнено, увімкнено), (увімкнено, вимкнено), (вимкнено, увімкнено) та (вимкнено, вимкнено). Серед них тільки (увімкнено, увімкнено) горять всі лампочки, тому нам слід надрукувати 1.

Приклад вхідних даних

2 2
2 1 2
1 2
0 1

Приклад вихідних даних

1

Приклад вхідних даних

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

Приклад вихідних даних

0

Приклад вхідних даних

5 2
3 1 2 5
2 2 3
1 0

Приклад вихідних даних

8