Simpatik naxışlar - 3#4809
BrokenTiles şirkəti varlı müştərilərin həyətlərinə ağ-qara tiles (döşəmə) üçün naxışlar hazırlamağı planlaşdırır, burada hər bir tile-in ölçüsü 1 \times 1 metrdir. Bütün bu müştərilərin həyətləri hazırda dəbdə olan ölçüdə, yəni n \times m metr ölçüsündə düzbucaqlıdır.
Maliyyə planını hazırlayarkən, şirkətin direktoru iki əsas problemlə üzləşdi: birincisi, hər yeni müştəri təbii olaraq başqa heç bir müştərinin naxışına bənzəməyən unikal bir naxış istəyəcək; ikincisi isə naxış gözoxşayan, yəni estetik cəhətdən cəlbedici olmalıdır.
Araşdırmalar göstərir ki, naxış yalnız o halda gözəl hesab olunur ki, heç bir 2 \times 2 ölçülü kvadratda bütövlükdə eyni rəngli tiles olmasın.
Maliyyə planını yekunlaşdırmaq üçün direktor məhz belə ölçüdə olan cəlbedici naxışların sayını tapmalıdır ki, neçə müştəriyə xidmət göstərə biləcəklərini hesablasın. Ona bu hesablamada yardımcı olun.
Girişin ilk sətrində üç təbii ədəd verilir: , , və (1 \leq n \leq 10^{100}, 1 \leq m \leq 5, 1 \leq p \leq 10000).
Çıxışda bir ədəd verin — ölçüsü n \times m olan həyət üçün düzülə biləcək müxtəlif, cəlbedici naxışların sayını, moduluna görə hesablayıb çıxışa yazın. Qeyd: Yerdəyişmə, fırlanma və ya güzgü əks olunması ilə biri digərinə çevrilən naxışlar fərqli hesab olunur.
Nümunə 1