### Problem Statement

In graph theory, an independent set or stable set is a set of vertices in a graph such that no two of the vertices are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two.

Similarly, we can define a k-stable set as a set of vertices in a graph such that each vertex in the set has at most k adjacent vertices that are also in the set. So the 0-stable set is the original stable set.

You will be given a String[] graph, representing an undirected, acyclic, connected graph. The j-th character of the i-th element of graph will be 'Y' if vertices i and j are connected, or 'N' otherwise. Return a int[] containing exactly n elements, where n is the number of elements in graph. The i-th element should be the number of distinct i-stable sets in the graph modulo 112901989, where i is a 0-based index.

### Definition

 Class: TreeCount Method: count Parameters: String[] Returns: int[] Method signature: int[] count(String[] graph) (be sure your method is public)

### Constraints

-graph will contain between 1 and 50 elements, inclusive.
-Each element of graph will contain exactly N characters, where N is the number of elements in graph.
-Each character in graph will be either 'Y' or 'N'.
-The j-th character of the i-th element of graph will equal to the i-th character of the j-th element.
-The i-th character of the i-th element of graph will be 'N'.
-The graph will represent a tree.

### Examples

0)

 `{"NYY", "YNN", "YNN"}`
`Returns: {5, 7, 8 }`
 The tree is 1-0-2. The 5 0-stable sets are {}, {0}, {1}, {2}, {1, 2}. The 7 1-stable sets are all the subsets except {0, 1, 2}. There are 2^3 subsets total, and each one is a 2-stable set.
1)

 `{"N"}`
`Returns: {2 }`
2)

 `{"NYNNNYY", "YNNNNNN", "NNNNNNY", "NNNNNNY", "NNNNNNY", "YNNNNNN", "YNYYYNN"}`
`Returns: {44, 73, 104, 124, 128, 128, 128 }`
3)

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

 `{"NYYYYY", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN"}`
`Returns: {33, 38, 48, 58, 63, 64 }`

#### Problem url:

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

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13504&pm=9844

yuhch123

#### Testers:

PabloGilberto , legakis , Olexiy , ivan_metelsky

#### Problem categories:

Dynamic Programming