U gradiću u kom žive Kići i Ćiki postoji jednanagradna igrica. U igrici ima m učesnika. Svaki učesnikizabere neko od prvih n slova engleske abecede. Onda se od tihslova napravi jedna reč - slovo koje je izabrao prvi učesnik jeprvo slovo te reči, itd. Na kraju se prebroji koliko puta sesvako od slova pojavljuje u toj reči. Svi oni koji su izabralislovo koje se pojavljuje neparan broj puta dobijaju brodić.

Učesnici naravno ne znaju koja će slova ostali birati, alipošto su Kići i Ćiki jako simpatični oni su uspeli da odsvakog učesnika saznaju po nekoliko slova koja on sigurnoneće izabrati.

I sada oni imaju zadatak za vas: za svako od prvih n slova oniće vam reći da li žele da se ono pojavi paran broj puta,neparan broj puta ili im je svejedno. Vi treba da im kažetekoliko od reči koje se mogu dobiti u ovoj igrici zadovoljavaju tenjihove uslove (pretpostavljamo da niko nije slagao Kićija iĆikija). Pošto broj reči može biti velik, dovoljno je da imkažete ostatak pri deljenju tog broja sa 10.007.

Ulaz:

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalaze se dva broja,n i m (broj slova iz alfabeta koja mogu biti korišćena i broj učesnika u igri). Sledi m redova sa po n brojeva u svakom od njih - u i-tom od tih redova j-ti broj je 0 ako i-ti učesnik sigurnoneće izabrati j-to slovo, odnosno 1 ako možda hoće. Uposlednjem redu datoteke nalazi se još n brojeva - j-ti odnjih je 0 ako Kići i ćiki žele da se j-to slovo pojaviparan broj puta, 1 ako žele da se pojavi neparan broj puta,odnosno -1 ako im je svejedno.

Izlaz:

(Izlazni podaci se ispisuju na standardni izlaz) U izlaznoj datoteci treba da se nalazi jedanbroj - broj reči koje zadovoljavaju Kićijeve i ćikijeveuslove po modulu 10.007.

Ograničenja:

Neka je k_i broj jedinica u redu datoteke koji odgovarai-tom učesniku.

• u 20% test primera: n ≤ 10, m ≤ 6, 1 ≤ k_i ≤ n
• u 20% test primera: n ≤ 15, m ≤ 12, 1 ≤ k_i ≤ 3
• u ostalim primerima: n ≤ 15, m ≤ 50, 1 ≤ k_i ≤ n

Primer 1:

5 4
1 0 0 0 1
1 1 1 0 0
1 0 1 0 0
0 0 1 0 0
1 -1 0 -1 -1

3

Objašnjenje.

Prvi učesnik će izabrati neko od slova {A,E}, drugi {A,B,C}, treći {A,C}i četvrti {C}. Traži nam se broj reči u kojima se A pojavljuje neparan a C paran brojputa. Moguće su sledeće reči:

Među njima reči koje zadovoljavaju uslov su ABCC, EACC, ECAC - ima ih 3.