Tournament winner placements

Time limit2sMemory limit512 MB

Summary

Count, over all N! seatings of N players in a fixed bracket, how many make each player the champion given a full win/loss table.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, Bit manipulation, Divide and conquer
Solved: No attempts yet

Problem

A single elimination tournament has N contestants, and N is a power of two. The contestants are placed one per seat in seats numbered 0 to N-1. In the first round adjacent seats play each other: seat 0 against seat 1, seat 2 against seat 3, and so on. Only the winner of each match advances, and the same pairing continues until one contestant is left.

The bracket for N = 8 looks like this. The numbers on the left are seat numbers.

0 --+
    +--+
1 --+  |
       +--+
2 --+  |  |
    +--+  |
3 --+     |
          +-- champion
4 --+     |
    +--+  |
5 --+  |  |
       +--+
6 --+  |
    +--+
7 --+

The outcome of a match between any two people is fixed in advance. A placement therefore determines a single champion.

Write a program that counts, for each person, how many placements make that person the champion. A placement is a permutation of the N people over the N seats, and two placements that differ in any seat are different. There are $N!$ placements in total.

Input

The first line contains the number of contestants N. ( $2 \le N \le 16$ , N is a power of two)

Each of the next N lines holds one row of the result table. In row i (counting from 0), character j (counting from 0) is the outcome of a match between person i and person j. The character Y means person i wins, and the character N means person j wins.

Character i of row i is always N. For any two different indices i and j, exactly one of character j of row i and character i of row j is Y.

Output

On the first line print the number of placements that make person 0 the champion, then person 1, and so on through person N-1, separated by single spaces. The largest possible answer is $16! = 20922789888000$ , so 64-bit integers are needed.

Examples3

Example 1
Input
```
2
NN
YN
```
Expected output
```
0 2
```
Example 2
Input
```
4
NYNY
NNYN
YNNY
NYNN
```
Expected output
```
8 0 16 0
```

Example 3

Input

8
NYNYNYNY
NNYNYNYY
YNNNNNNN
NYYNNYNY
YNYYNYYY
NYYNNNNN
YNYYNYNN
NNYNNYYN

Expected output

4096 8960 0 2048 23808 0 1408 0