Ailəvi estafet
Beytlandiya hökuməti 2012-ci ili Sağlamlıq İli elan etdi. Bu münasibətlə, milli paytaxt parkında illik ailə estafeti üçün bir qaçış zolağı tikmək qərara alındı. Milli park N x M metr ölçüsündə düzbucaqlı bir ərazidir və hər biri 1 m² olan kvadratlara bölünmüşdür. Başqa sözlə, park N sıra və M sütundan ibarət bir düzbucaqlı cədvələ uyğundur. Sıralar yuxarıdan aşağıya doğru birlə başlayaraq nömrələnir, sütunlar isə soldan sağa doğru birlə başlayaraq nömrələnir. Beləliklə, hər kvadrat (X, Y) cütü ilə təmsil olunur, burada X sıra nömrəsi, Y isə sütun nömrəsidir.
Əvvəlcə qaçış zolağının düzbucaqlı formada olması planlaşdırılırdı. Lakin Beytlandiya Təbiət Resursları Nazirliyinin ekoloqları, dünya standartlarına uyğun olaraq, onun xaç şəklində olmasını tövsiyə etdilər.
Xaç şəklində qaçış zolağı aşağıdakı kimi qurulur:
Eni bir kvadrat və uzunluğu H kvadrat olan üfüqi zolaq seçilir;
Eni bir kvadrat və uzunluğu V kvadrat olan, üfüqi zolaqla kəsişən şaquli zolaq seçilir. Burada H və V istənilən təbii ədədlərdir (həm üfüqi, həm də şaquli zolaqlara aid olan kvadrat əsas kvadrat adlanır);
Hər bir zolağın uzunluğu boyunca ortada müvafiq olaraq H - 1 və V - 1 metr uzunluğunda hasarlar quraşdırılır.
Estafet əsas kvadratda başlayır və bitir. Qaçış zolağı hasarın boyunca həyata keçirilir, şəkildə göstərildiyi kimi.
Şəkil №1. İkinci nümunənin təsviri, hər biri 6 bayt dəyərində olan 2 mümkün zolaq variantı.
Parkın kvadratları iki növdə ola bilər: ağac olan və ya ağac olmayan (boş kvadrat). Əgər kvadrat ağac ehtiva edirsə, onun bütün sahəsini tutduğunu hesab edəcəyik.
Qaçış zolağının tikinti dəyəri yalnız kvadratların sayından deyil, həm də onların növündən asılıdır. Məlumdur ki, boş kvadratın qaçış zolağı üçün təchiz edilməsi bir bayt (bayt - Beytlandiyanın milli valyutası) təşkil edir, ağac olan kvadratın təchiz edilməsi isə iki bayt təşkil edir, çünki ağac əvvəlcədən sökülməlidir.
Beytlandiya hökuməti qaçış zolağının yaradılması üçün S bayt ayırıb. Sizin vəzifəniz - xaç şəklində qaçış zolağının tikintisinin müxtəlif yollarının sayını müəyyən etməkdir. Qaçış zolağının tikintisinin iki yolu fərqli hesab olunur, əgər onlara uyğun kvadratlar çoxluğu və ya əsas kvadratlar fərqlidirsə.
Giriş verilənləri
Giriş faylının ilk sətri N, M (2 ≤ N, M ≤300) və S (1 ≤ S ≤ 10^9) olmaqla üç tam ədəd ehtiva edir, boşluqla ayrılmışdır.
Növbəti N sıra M simvoldan ibarət sətir dəyərləri ehtiva edir, parkı təsvir edir, i-ci sıra dəyərindəki j-ci simvol kvadratın növünü təsvir edir. '.' simvolu (ASCII 46) - (i, j) koordinatları olan kvadrat boşdur, '#' simvolu (ASCII 35) - (i, j) koordinatları olan kvadrat ağac ehtiva edir.
Çıxış verilənləri
Çıxış faylı bir tam ədəd ehtiva etməlidir - xaç şəklində qaçış zolağının tikintisinin müxtəlif yollarının sayı.