Yolların sayılması#1103

Yolların sayılması

1 saniyə

128 meqabayt

Çox asan

Verilmiş istiqamətli qraf $g$ üçün uzunluğu $k$ -dan kiçik olan fərqli dövrlərin sayını müəyyənləşdirin. Bu ədəd çox böyük ola biləcəyi üçün cavabı $m$ -ə görə modullaşdırılmış şəkildə çıxışa verin. Dövr dedikdə boş olmayan və şərt qoyulmamış ardıcıllıq başa düşülür; belə ki, ardıcıllığın hər bir elementi üçün növbəti elementə keçid üçün qrafda istiqamət mövcuddur və sonuncu elementdən birincisinə də keçid vardır. İki dövr o zaman fərqli sayılır ki, onların təyin edən ardıcıllıqları fərqlidir.

Girdi

Birinci sətirdə qrafdakı düyünlərin sayı $n$ ( $1 \leq n \leq 35$ 1 \leq n \leq 35), $k$ ( $1 \leq k \leq 1 0^{6}$ 1 \leq k \leq 10^6) və $m$ ( $1 \leq m \leq 1 0^{9}$ 1 \leq m \leq 10^9) verilir. Sonra $n$ sətir qrafı təsvir edir: $i$ -ci sətirin $j$ -ci simvolu istiqamətliliyi bildirən yaxınlıq matrisindəki girişə uyğundur: əgər $i$ -dən $j$ -ə qrafda istiqamətlənmiş kənar varsa, bu simvol 'Y', yoxdursa 'N' olacaq.

Çıxış

Qraf $g$ -də uzunluğu $k$ -dan kiçik olan fərqli dövrlərin sayını çap edin. Cavabı $m$ -ə görə çıxışa verin.

Nümunələr

Nümunə 1

Loading

1 \leq n \leq 35

1 \leq k \leq 1 0^{6}

1 \leq m \leq 1 0^{9}