### Problem Statement

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).

### Definition

 Class: TourCounting Method: countTours Parameters: String[], int, int Returns: int Method signature: int countTours(String[] g, int k, int m) (be sure your method is public)

### Notes

-The answer modulo m means that you must return the remainder of dividing the result by m.

### Constraints

-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.

### Examples

0)

 ```{"NYNY", "NNYN", "YNNN", "YNNN"}``` `6` `100`
`Returns: 12`
 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.
1)

 ```{"NYNNNNN", "NNYNNNN", "NNNYNNN", "NNNNYNN", "NNNNNYN", "NNNNNNY", "YNNNNNN"}``` `40` `13`
`Returns: 9`
 All cycles have lengths that are multiples of 7. For each starting node and each multiple of 7 there exists one cycle. There are 5 non-zero multiples of 7 that are less than 40 (7,14,21,28,35) and 7 possible starting nodes. Therefore, the total number of cycles is 5x7=35. 35 modulo 13 is 9.
2)

 ```{"NYNY", "NNNN", "YYNY", "NYNN"}``` `1000000` `1000000000`
`Returns: 0`
 The graph does not have cycles.
3)

 ```{"NY", "YN"}``` `1500` `1`
`Returns: 0`
 Any number modulo 1 is zero.
4)

 ```{"NYYNYYN", "YNYNYNY", "NYNYNYN", "YYYNYNY", "NNYYNNY", "NYYYNNY", "YYYYYYN"}``` `30` `100`
`Returns: 72`
5)

 ```{"NYYY", "YNYY", "YYNY", "YNYN"}``` `1000` `10000`
`Returns: 3564`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6386

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9986&pm=6386

soul-net

#### Testers:

PabloGilberto , brett1479 , Olexiy , lovro , Andrew_Lazarev

#### Problem categories:

Advanced Math, Dynamic Programming, Graph Theory, Recursion