Siltumtrase

Uzdevums

Siltumtrasei jāsavieno n×m rūtiņas liela taisnstūrveida apgabala kreisā augšējā stūra rūtiņas (1;1) augšējā mala ar labā apakšējā stūra rūtiņas (n;m) labo malu. Siltumtrases izbūvē var izmantot 1.zīmējumā redzamās četru veidu caurules, katra no kurām savieno divas vienas rūtiņas malas.

1.zīmējums. Cauruļu veidi.

Caurulēm siltumtrasē jābūt iebūvētām tieši tā kā redzams zīmējumā, bez pagriešanas. Tāpēc neviena caurule nevar savienot ne rūtiņas kreiso malu ar augšējo, ne labo malu ar apakšējo. Izbūvētās siltumtrases caurulēm jābūt savienotām, t.i., ja divu blakus rūtiņu caurules pieder siltumtrasei, tad cauruļu galiem abās rūtiņās ir jāpienāk pie šo rūtiņu kopīgās malas. Visai siltumtrasei ir jāatrodas dotajā taisnstūrveida apgabalā - neviens tās posms nedrīkst atrasties ārpus tā. Sākotnēji katra apgabala rūtiņa var būt tukša (un tad tajā var iebūvēt jaunu cauruli), vai arī tajā var atrasties: a) senāk ierakta caurule, kuru var izmantot kā posmu siltumtrasē, bet tās vietā nedrīkst ierakt citu cauruli; b) apstādījumi. Caur šādu rūtiņu siltumtrase nedrīkst iet. Piemērs apgabalam ar apstādījumiem un senāk ieraktām caurulēm (n=4, m=5) dots 2.zīmējumā. Rūtiņā (4;2) atrodas apstādījumi.

2.zīmējums. Apgabala piemērs.

Šim apgabalam siltumtrasi iespējams izbūvēt trīs dažādos veidos, kas parādīti 3.zīmējumā.

3.zīmējums. Iespējamie siltumtrases izbūves varianti.

Uzrakstiet programmu, kas dotam apgabalam nosaka, cik dažādos veidos iespējams izbūvēt siltumtrasi.

Ievaddati

Teksta faila trase.in pirmajā rindā dotas divu naturālu skaitļu n (n <= 10) un m (m <= 10) vērtības, kas atdalītas ar tukšumsimbolu. Nākošajās m faila rindās dots pa n cipariem katrā. Faila i+1-ās rindas j-tais cipars atbilst apgabala i-tās rindas j-tās kolonas rūtiņai. Cipars 0 apzīmē tukšu rūtiņu, cipari no 1 līdz 4 apzīmē rūtiņā iebūvētu cauruli saskaņā ar 1.zīmējumu, bet 5 nozīmē, ka attiecīgajā rūtiņā ir apstādījumi. Katrā rindā starp diviem blakus esošiem cipariem ir viens tukšumsimbols.

Izvaddati

Teksta faila trase.out pirmajā rindā jāizvada viens vesels skaitlis - dažādo iespējamo siltumtrases izbūves variantu skaits.

Piemērs

trase.in	trase.out
4 5 0 0 3 2 0 4 0 5 4 0 0 0 4 0 1 0 0 3 0 0	3