favorite We need a little bit of your help to keep things running, click on this banner to learn more

Floyd - Warshall + Transitive closure

Tour Counting

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 (1n35) and the numbers k (1k106) and m (1m109). 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.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
4 6 100
Output example #1
Source Summer School 2010, Sebastopol, Day M.Medvedev