### Problem Statement

John and Brus have become very famous people all over the world, especially in Bolivia. Once they decided to visit their fan club in Bolivia. John has an old map of Bolivia which shows all of its cities and the roads connecting them. All roads are bidirectional, meaning they can be traversed in both directions. Since the map is old, it's possible that some additional roads have been built since the map was produced. However, roads are never destroyed in Bolivia, so all the roads on the map still exist.

Brus has discovered on the Internet that each pair of Bolivian cities now has at least one and at most two simple paths connecting them. A path between cities A and B is a sequence of cities starting with A and ending with B such that there's a road between each pair of consecutive cities in the sequence. The path is considered simple if it consists of distinct cities.

You are given a String[] map. The j-th character of the i-th element of map will be 'Y' if there is a road between the i-th and j-th cities on the old map, or 'N' otherwise. Return the number of ways John and Brus can add new roads to the old map modulo 1234567891. Two ways are considered different if the sets of added roads are distinct. The order in which roads are added does not matter.

### Definition

 Class: TheCitiesAndRoadsDivOne Method: find Parameters: String[] Returns: int Method signature: int find(String[] map) (be sure your method is public)

### Constraints

-map will contain between 1 and 20 elements, inclusive.
-Each element of map will contain exactly n characters, where n is the number of elements in map.
-Each character of map will be either 'Y' of 'N'.
-The j-th character of the i-th element of map will be equal to the j-th character of the i-th element of map.
-The i-th character of the i-th element of map will be 'N'.
-There will be at least one way for John and Brus to add new roads to the old map.

### Examples

0)

 ```{"NN", "NN"}```
`Returns: 1`
 There is only one way - connect the cities with a single road.
1)

 ```{"NNY", "NNN", "YNN"}```
`Returns: 3`
 There are three possible ways - connect the second city with the first one, with the third one or with both.
2)

 ```{"NY", "YN"}```
`Returns: 1`
3)

 ```{"NYNN", "YNNN", "NNNY", "NNYN"}```
`Returns: 10`
4)

 ```{"NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN", "NNNNNNNNNNNN"}```
`Returns: 1137797187`
5)

 `{"N"}`
`Returns: 1`
6)

 ```{"NYYNN", "YNYNN", "YYNNN", "NNNNY", "NNNYN"}```
`Returns: 6`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14146&pm=10773

Vasyl[alphacom]

#### Testers:

PabloGilberto , connect4 , ivan_metelsky

#### Problem categories:

Dynamic Programming