eolymp
bolt
Try our new interface for solving problems
Problems

Tour Counting

Tour Counting

Time limit 1 second
Memory limit 128 MiB

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.

Input data

The first line contains the number of nodes in the graph n (1n35) and the numbers k (1k10^6) and m (1m10^9). 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).

Output data

Print the number of distinct cycles in graph g that have length less than k. Print the answer modulo m.

Examples

Input example #1
4 6 100
NYNY
NNYN
YNNN
YNNN
Output example #1
12
Source Summer School 2010, Sebastopol, Day M.Medvedev