;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defun f2-solve-linear-system! (matrix vector)
  "Solves Ax = b on GF(2) and returns a root if it exists. Otherwise it returns
NIL. In addition, this function returns the rank of A as the second value. This
function destructively modifies MATRIX and VECTOR.

The width of A must be multiple of 64."
  (declare ((simple-array bit (* *)) matrix)
           (simple-bit-vector vector))
  (destructuring-bind (m n) (array-dimensions matrix)
    (declare ((integer 0 #.most-positive-fixnum) m n))
    (multiple-value-bind (n/64 rem) (floor n 64)
      (assert (zerop rem))
      (let* ((storage (array-storage-vector matrix))
             (rank 0))
        (declare (fixnum rank))
        (dotimes (target-col n)
          (let* ((pivot-row (do ((i rank (+ 1 i)))
                                ((= i m) -1)
                              (unless (zerop (aref matrix i target-col))
                                (return i)))))
            (when (>= pivot-row 0)
              (let ((pivot-row/64 (floor (array-row-major-index matrix pivot-row 0) 64))
                    (rank-row/64 (floor (array-row-major-index matrix rank 0) 64)))
                ;; swap rows
                (rotatef (aref vector rank) (aref vector pivot-row))
                (loop for k from 0 below n/64
                      do (rotatef (sb-kernel:%vector-raw-bits storage (+ rank-row/64 k))
                                  (sb-kernel:%vector-raw-bits storage (+ pivot-row/64 k))))
                ;; eliminate the column
                (dotimes (i m)
                  (unless (or (= i rank) (zerop (aref matrix i target-col)))
                    (setf (aref vector i) (logxor (aref vector i) (aref vector rank)))
                    (loop with base/64 = (floor (array-row-major-index matrix i 0) 64)
                          for k below n/64
                          do (setf (sb-kernel:%vector-raw-bits storage (+ base/64 k))
                                   (logxor (sb-kernel:%vector-raw-bits storage (+ base/64 k))
                                           (sb-kernel:%vector-raw-bits storage (+ rank-row/64 k))))))))
              (incf rank))))
        (if (loop for i from rank below m
                  always (zerop (aref vector i)))
            (values vector rank)
            (values nil rank))))))

(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read))
         (n64 (* 64 (ceiling n 64)))
         (m (read))
         (mat (make-array (list m n64) :element-type 'bit :initial-element 0))
         (ps (make-array m :element-type 'bit :initial-element 0)))
    (declare (uint8 n m))
    (dotimes (i m)
      (dotimes (_ (read))
        (let ((j (- (read) 1)))
          (setf (aref mat i j) 1))))
    (dotimes (i m)
      (setf (aref ps i) (read)))
    (multiple-value-bind (root rank) (f2-solve-linear-system! mat ps)
      (if root
          (println (expt 2 (- n rank)))
          (println 0)))))

#-swank(main)


Measured memory_bytes: 13024