Tour Counting#1103
Given a directed graph , determine the number of distinct cycles with length less than . Since this number can be large, output the answer modulo . A cycle is a non-empty sequence of nodes (not necessarily distinct) such that there is an edge from each node to the next, and an edge from the last node to the first. Two cycles are considered distinct if their defining sequences are different.
The first line contains the number of nodes in the graph (1 \leq n \leq 35), (1 \leq k \leq 10^6), and (1 \leq m \leq 10^9). The next lines describe the graph: the -th character of the -th row in the adjacency matrix indicates whether there is an edge from node to node ('Y' means there is an edge, 'N' means there is not).
Print the number of distinct cycles in with length less than . Print the answer modulo .
Example 1