토너먼트 우승 배치 세기

N명이 참가하는 단판 승부 토너먼트가 있다. N은 2의 거듭제곱이다. 참가자를 0번부터 N-1번까지 번호가 붙은 자리에 한 명씩 배치하면, 1라운드에서는 자리 0과 자리 1, 자리 2와 자리 3처럼 이웃한 두 자리가 맞붙는다. 각 경기의 승자만 다음 라운드로 올라가고, 한 명이 남을 때까지 같은 방식으로 진행한다.

N = 8일 때의 대진표는 다음과 같다. 왼쪽의 숫자는 자리 번호이다.

0 --+
    +--+
1 --+  |
       +--+
2 --+  |  |
    +--+  |
3 --+     |
          +-- 우승
4 --+     |
    +--+  |
5 --+  |  |
       +--+
6 --+  |
    +--+
7 --+

두 사람이 맞붙었을 때 누가 이기는지는 미리 정해져 있다. 그래서 배치가 정해지면 우승자도 하나로 정해진다.

각 사람이 우승하는 배치가 몇 가지인지 세는 프로그램을 작성하시오. 배치는 N명을 N개의 자리에 나열한 순열이고, 한 자리라도 다르면 다른 배치로 센다. 전체 배치의 수는 $N!$이다.

첫째 줄에 참가자 수 N이 주어진다. ($2 \le N \le 16$, N은 2의 거듭제곱)

다음 N개의 줄에 경기 결과표가 주어진다. 위에서 i번째 줄(0부터 센다)의 j번째 글자(0부터 센다)는 i번 사람과 j번 사람이 맞붙었을 때의 결과이다. 이 글자가 Y이면 i번 사람이 이기고, N이면 j번 사람이 이긴다.

i번째 줄의 i번째 글자는 항상 N이다. 서로 다른 i와 j에 대해 i번째 줄의 j번째 글자와 j번째 줄의 i번째 글자 중 정확히 하나만 Y이다.

첫째 줄에 0번 사람부터 N-1번 사람까지 각 사람이 우승하는 배치의 수를 공백 하나로 구분해 차례대로 출력한다. 답은 최대 $16! = 20922789888000$이므로 64비트 정수가 필요하다.