Enerji Şəbəkəsi#6051
Ötən kirayəçinin vaxtsız vəfatından sonra, özünüzü Lord Vader-in özü tərəfindən Ölüm Ulduzunun yeni "baş memarı" vəzifəsinə təyin olunmuş tapdınız. Sizə Ölüm Ulduzunun hər bir sektorunda güc paylanması üçün naqil sistemini dizayn etmək tapşırılıb. Uğurunuzdan asılı olaraq həyatınızın təhlükədə olduğunu bilə-bilə, ən yaxşısını seçmək üçün bütün etibarlı naqil konfiqurasiyalarını dəqiq və hərtərəfli şəkildə qeyd etməyə qərar verdiniz.
Sizə Ölüm Ulduzunun xəritəsi verilir, m×n ölçüsündə bir şəbəkə şəklində, hansı ki, hüceyrələr sektorlara uyğun gəlir. Xəritədəki sektorlardan biri dəqiq bir enerji stansiyasıdır; qalan sektorlar isə ya yaşayış yerləri, ya da anbar bölmələridir. Siz, şaquli və ya üfüqi olaraq bitişik olan hər hansı iki qeyri-anbar sektoru arasında bir əlaqə yerləşdirmək seçiminə maliksiniz. Etibarlı bir naqil konfiqurasiyası belədir ki:
Hər bir yaşayış sektoru ya birbaşa, ya da dolayı yolla enerji stansiyası sektoruna bağlıdır və
Mümkün qədər az əlaqə istifadə olunur (yəni, hər hansı bir əlaqənin çıxarılması bəzi yaşayış yerlərinin enerji stansiyasından ayrılmasına səbəb olar).
Verilən xəritə üçün neçə etibarlı naqil konfiqurasiyası mövcuddur?
Girişdə bir neçə test halı olacaq. Hər bir test halı m və n cüt tam ədədlərini (burada 1 ≤ m ≤ 8 və 1 ≤ n ≤ 8) ehtiva edən bir sətirlə başlayır. Növbəti m sətir hər biri n simvol ehtiva edir, Ölüm Ulduzunun xəritəsini təmsil edir. Xəritədə dəqiq bir enerji stansiyası (P) ilə işarələnmiş bir sektor olacaq; qalan bölmələr isə ya yaşayış yerləri (.) ya da anbar bölmələri (#) olacaq. Sizə ən azı bir etibarlı naqil konfiqurasiyasının mövcud olduğu zəmanət verilir. Girişin sonu "0 0" ehtiva edən bir sətirlə göstərilir və işlənməməlidir.
Hər bir giriş test halı üçün, etibarlı naqil konfiqurasiyalarının sayını 1000000000 ilə mod olaraq çap edin.
Nümunə 1