시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 26 13 12 63.158%

문제

총 N(N은 2의 제곱꼴)명이 참가하는 토너먼트 대회가 있다. 

아래 그림은 N = 8인 경우의 토너먼트 구조이다.

위치 0 --
        |--|
위치 1 --   |
           |--|
위치 2 --   |  |
        |--|  |
위치 3 --      |
              |--
위치 4 --      |
        |--   |
위치 5 --   |  |
           |--
위치 6 --   |
        |--
위치 7 --

어떤 사람 i가 j와 경기를 했을 때의 경기 결과는 이미 알려져있다. 따라서, 어떤 사람이 어떤 위치에 배정되는지 결정되면 우승자도 자동으로 결정지어지게 된다.

각 사람이 우승할 수 있는 위치 배치의 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 참가자의 수 N (2 ≤ N ≤ 16, N은 2의 제곱꼴)이 주어진다.

둘째 줄부터 N개의 줄에는 각 사람 i가 다른 사람 j와 경기를 했을 때, 이기는지 지는지를 나타내는 문자가 주어진다. i번째 줄의 j번째 글자는 i번 사람과 j번 사람의 결과를 나타내며, Y인 경우는 i가 이기는 것이고 N인 경우는 j가 이기는 것이다.

자기 자신과의 경기 결과는 항상 N이며, i번째 줄의 j번째 글자와 j번째 줄의 i번째 글자중 하나는 항상 Y이다.

출력

첫째 줄에 각 사람이 우승할 수 있는 위치 배정의 경우의 수를 공백으로 구분해서 0번 사람부터 차례대로 출력한다.

예제 입력 1

2
NN
YN

예제 출력 1

0 2

예제 입력 2

4
NYNY
NNYN
YNNY
NYNN

예제 출력 2

8 0 16 0

예제 입력 3

8
NYNYNYNY
NNYNYNYY
YNNNNNNN
NYYNNYNY
YNYYNYYY
NYYNNNNN
YNYYNYNN
NNYNNYYN

예제 출력 3

4096 8960 0 2048 23808 0 1408 0