Fişierul intrare/ieşire:	go2.in, go2.out	Sursă	Algoritmiada 2012, Runda 4
Autor	Cosmin Silvestru Negruseri	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.075 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Go2

Claudia, plictisita sa mai joace Go, incepe sa-si puna tot felul de intrebari despre joc. Avand inclinari artistice si o imaginatie bogata isi pune problema aflarii numarului de table dreptunghiulare de marime N * M din jocul GO astfel incat fiecare pozitie de pe tabla sa aiba printre vecinii sai (sus, jos, stanga, dreapta) un numar par de piese (nu se face distinctie intre piesele primului jucator si piesele celui de-al doilea). Mai apoi s-a intrebat cate astfel de table exista astfel incat la final anumite pozitii de pe table sa fie ocupate si anumte pozitii sa fie libere. Problema s-a dovedit prea grea pentru Claudia asa ca va roaga pe voi sa o rezolvati.
Intrucat numarul acesta poate fi foarte mare ea va roaga sa afisati restul impartirii sale la 1.000.000.007.

Date de intrare

Fişierul de intrare go2.in va contine pe prima linie 2 numere nature N si M ce reprezinta numarul de linii respectiv coloane ale tablei.
Urmatoarele N linii vor contine cate M caractere. Daca caracterul j de pe linia i este

• 0 atunci la final tabla trebuie sa nu aiba vreo piesa pe aceasta pozitie
• 1 atunci la final tabla trebuie sa aiba exact o piesa pe aceasta pozitie
• ? atunci la final poate sa aiba sau sa nu aiba o piesa pe aceasta pozitie

Date de ieşire

Fişierul de ieşire go2.out trebuie sa contina exact un numar reprezentand numarul de table cu N linii si M coloane ce respecta restrictiile din enunt si din fisierul de intrare.

Restricţii

• 1 ≤ N, M ≤ 100
• Pe o pozitie (i, j) se poate afla maxim o piesa
• Vecinii unei pozitii (i, j) sunt (i - 1, j), (i, j - 1), (i + 1, j) si (i, j + 1)

Exemplu

Explicaţie

Pentru primul caz solutiile sunt
010
101
010
si
111
101
111

Cum se trimit solutii?