Verilmiş istiqamətlənmiş g qrafına görə uzunluğu k-dan az olan müxtəlif dövrlərin sayını təyin etmək tələb olunur. Belə ki, bu say böyük ola bilər, onu m moduluna görə hesablayın. Hər bir əvvəlki təpədən növbəti təpəyə til gedən, həmçinin sonuncu təpədən birinci təpəyə gedən til mövcuddursa, boş olmayan təpələr ardıcıllığı (müxtəlif olması vacib deyil) dövr adlanır. Əgər təpələr ardıcıllığı, onların təyinediciləri müxtəlifdirsə, iki dövr müxtəlif sayılır.

Giriş verilənləri

İlk sətir qrafın təpələrinin n (1 ≤ n ≤ 35) sayını, k (1 ≤ k ≤ 106) və m (1 ≤ m ≤ 109) ədədlərini ehtiva edir. Növbəti n sətir qrafı təsvir edir: qonşuluq matrisinin i –ci sətrinin j -ci işarəsi i təpəsindən j təpəsinə tilin olduğunu bildirir ('Y' tilin olduğunu, 'N' isə olmadığını bildirir).

Çıxış verilənləri

g–dəki uzunluğu k-dan az olan müxtəlif dövrlərin sayını verməli. Bütün nəticələri m modluna görə verməli.