Подсчет путей
Подсчет путей
По заданному ориентированному графу g необходимо определить количество разных циклов, имеющих длину меньше k. Поскольку это количество может быть большим, вычислить его следует по модулю m. Циклом называется непустая последовательность вершин (необязательно различных), в которой из каждой предыдущей вершины в следующую ведет ребро, а также существует ребро, ведущее из последней вершины в первую. Два цикла считаются различными, если последовательности вершин, их определяющие, разные.
Входные данные
Первая строка содержит количество вершин в графе n (1 ≤ n ≤ 35) и числа k (1 ≤ k ≤ 106
) и m (1 ≤ m ≤ 109
). Следующие n строк описывают граф: j -ый символ i - ой строки матрицы смежности указывает на присутствие ребра, ведущего из вершины i в вершину j ('Y' означает, что ребро есть, 'N' означает, что нет).
Выходные данные
Вывести одно число - количество разных циклов в g, длины которых меньше чем k. Вывести результат по модулю m.
4 6 100 NYNY NNYN YNNN YNNN
12