**2 人解决**，8 人已尝试。

**4 份提交通过**，共有 20 份提交。

**9.5** EMB 奖励。

**单点时限: **10.0 sec

**内存限制: **256 MB

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, return 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. See example 0 for further clarification.

g will be given as a String[] where the jth character of the ith element indicates whether there is an edge from node i to node j (‘Y’ means there is one, and ‘N’ means there is not).

-g will have between 1 and 35 elements, inclusive.

-Each element of g will have exactly N characters, where N is the number of elements in g.

-Each character of each element of g will be ‘Y’ or ‘N’.

-The ith character of the ith element of g will be ‘N’.

-k will be between 1 and 1000000 (106), inclusive.

-m will be between 1 and 1000000000 (109), inclusive.

First line is n ,stand for the number of the elements in graph g,then n*n matrix where the jth character of the ith element indicates whether there is an edge from node i to node j (‘Y’ means there is one, and ‘N’ means there is not).And then two number k,m discrible above.

the number of distinct cycles in g that have length less than k.Since this number can be really big, return the answer modulo m.

Input

4 NYNY NNYN YNNN YNNN 6 100 7 NYNNNNN NNYNNNN NNNYNNN NNNNYNN NNNNNYN NNNNNNY YNNNNNN 40 13

Output

12 9 The possible cycles with length less than 6 are: (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) Note that (0,3), (3,0) and (0,3,0,3) are all considered different.

**2 人解决**，8 人已尝试。

**4 份提交通过**，共有 20 份提交。

**9.5** EMB 奖励。

题目标签