import Control.Monad
import Data.List
main=do
 [n,m]<-map read.words<$>getLine
 ss<-replicateM m (map read.words<$>getLine)
 pn<-map read.words<$>getLine
 let ns=n`div`2
     aho=[x1:x2:x3:x4:x5:x6:x7:x8:x9:x10:[]|x1<-[1,0],x2<-[1,0],x3<-[1,0],x4<-[1,0],x5<-[1,0],x6<-[1,0],x7<-[1,0],x8<-[1,0],x9<-[1,0],x10<-[1,0]]
     s=zip pn (map (\(x:xs)->(x,xs)) ss)
     ans=foldl (\x y->filter(\a->let pl=fst(snd s);pp=fst s;ps=snd(snd s);p1=filter(\l->if length l`mod`2==pp then True else False)(nub[drop x1 (take y1 r)|r<-ps,x1<-[0..pl],y1<-[0..pl],y1>x1]) in filter(\d->if all(\u j->j!!(u-1)==1)p1 x then True else False))) aho s
     print$(length ans)`div`(2^(10-n))