ADA University - January 30
You are given a directed graph g, and you must determine the number of distinct cycles in g that have length less than k. Since this number can be really big, find the answer modulo m. A cycle is a non-empty sequence of nodes (not necessarily distinct) in which there is an edge from each node to the next node, and an edge from the last node in the sequence to the first node. Two cycles are distinct if their sequences are not identical.
The first line contains the number of nodes in the graph n (1 ≤ n ≤ 35) and the numbers k (1 ≤ k ≤
106) and m (1 ≤ m ≤
109). Next n lines describe the graph: the j-th character of the i-th line of adjacency matrix indicates whether there is an edge from node i to node j ('Y' means there is one, and 'N' means there is not).
Print the number of distinct cycles in graph g that have length less than k. Print the answer modulo m.
4 6 100 NYNY NNYN YNNN YNNN