### Problem Statement

There are N cities in a country, numbered 0 to N-1. Each pair of cities is connected by a bidirectional road.

John plans to travel through the country using the following rules:
• He must start in one city and end in another city after travelling exactly N-1 roads.
• He must visit each city exactly once.
• You are given a String[] roads. If the j-th character of the i-th element of roads is 'Y', he must travel the road that connects city i and city j.
For example, if there are three cities, and he wants to travel the road between city 0 and city 1, there are 4 possible paths: 0->1->2, 1->0->2, 2->0->1, 2->1->0. Paths 0->2->1 and 1->2->0 are not allowed because they do not allow him to travel the road between city 0 and city 1.

Return the number of paths he can choose, modulo 1,000,000,007.

### Definition

 Class: HamiltonPath Method: countPaths Parameters: String[] Returns: int Method signature: int countPaths(String[] roads) (be sure your method is public)

### Constraints

-roads will contain between 2 and 50 elements, inclusive.
-Each element of roads will contain n characters, where n is the number of elements in roads.
-Each character in roads will be 'Y' or 'N'.
-The i-th character in the i-th element of roads will be 'N'.
-The j-th character in the i-th element of roads and the i-th character in the j-th element of roads will be equal.

### Examples

0)

 ```{"NYN", "YNN", "NNN"}```
`Returns: 4`
 The example from the problem statement.
1)

 ```{"NYYY", "YNNN", "YNNN", "YNNN"}```
`Returns: 0`
 It's impossible to travel all these roads while obeying the other rules.
2)

 ```{"NYY", "YNY", "YYN"}```
`Returns: 0`
 This is also impossible.
3)

 ```{"NNNNNY", "NNNNYN", "NNNNYN", "NNNNNN", "NYYNNN", "YNNNNN"}```
`Returns: 24`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13906&pm=10572

rng_58

#### Testers:

PabloGilberto , connect4 , ivan_metelsky

#### Problem categories:

Graph Theory, Math