eolymp
Соревнования

ADA University - January 30

Подсчет путей

По заданному ориентированному графу g необходимо определить количество разных циклов, имеющих длину меньше k. Поскольку это количество может быть большим, вычислить его следует по модулю m. Циклом называется непустая последовательность вершин (необязательно различных), в которой из каждой предыдущей вершины в следующую ведет ребро, а также существует ребро, ведущее из последней вершины в первую. Два цикла считаются различными, если последовательности вершин, их определяющие, разные.

Входные данные

Первая строка содержит количество вершин в графе n (1n35) и числа k (1k106) и m (1m109). Следующие n строк описывают граф: j -ый символ i - ой строки матрицы смежности указывает на присутствие ребра, ведущего из вершины i в вершину j ('Y' означает, что ребро есть, 'N' означает, что нет).

Выходные данные

Вывести одно число - количество разных циклов в g, длины которых меньше чем k. Вывести результат по модулю m.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
4 6 100
NYNY
NNYN
YNNN
YNNN
Выходные данные #1
12
Источник Летняя Школа 2010, Севастополь, день М.Медведева