Counting Cycles

You are given a directed graph $G$. Write a program that counts the distinct cycles of length less than $K$. The count can be very large, so print it modulo $M$.

A cycle is a sequence of nodes, and the same node may appear more than once. There must be an edge from each node to the next node, and there must also be an edge from the last node to the first node. The length of a cycle is the number of nodes in the sequence. Two sequences in a different order count as different cycles. For example, $(0, 1, 2)$ and $(1, 2, 0)$ are different cycles.

The nodes are numbered from $0$ to $N-1$.

The first line contains the number of nodes $N$ of the graph $G$, followed by $K$ and $M$. ($1 \le N \le 35$, $1 \le K \le 10^6$, $1 \le M \le 10^9$)

Each of the next $N$ lines gives the edges of the graph as an adjacency matrix. The $j$-th character of the $i$-th line describes the edge from node $i$ to node $j$. Y means the edge exists and N means it does not. The graph has no loops, so the $i$-th character of the $i$-th line is always N.

Print the number of distinct cycles of length less than $K$, modulo $M$, on the first line.

In the first example, the cycles of length less than $6$ are the following.

• $(0,3)$, $(3,0)$, $(0,1,2)$, $(1,2,0)$, $(2,0,1)$, $(0,3,0,3)$, $(3,0,3,0)$, $(0,1,2,0,3)$, $(0,3,0,1,2)$, $(1,2,0,3,0)$, $(2,0,3,0,1)$, $(3,0,1,2,0)$