조작된 대진표

프로 테니스 협회가 프로 선수들이 겨루는 대회를 연다. 대회는 한 번 지면 탈락하는 녹아웃 토너먼트로 치르고, 대진표를 짜는 일은 내가 맡았다.

참가자 전원의 상세 전적 보고서가 있다. 보고서에는 참가자 모든 쌍의 최근 경기 결과가 들어 있고, 자료를 살펴보니 승패는 상대가 누구냐에만 달려 있었다. $i$번 선수와 $j$번 선수가 붙으면 언제나 같은 쪽이 이긴다.

참가자 중에 친한 친구가 있어서 그 친구가 금메달을 받기를 바란다. 그래서 친구가 우승하는 대진표가 몇 가지인지 알고 싶다. 참가자가 많아 손으로 세기는 어려우니, 친구가 금메달을 따는 대진표의 개수를 세는 프로그램을 작성하라.

속임수를 들키지 않으려면 억지스러운 대진표를 만들면 안 된다. 그래서 토너먼트 트리의 높이를 최소로 해야 한다.

대진표는 $N$명의 선수가 잎에 한 명씩 놓인 이진 트리다. 내부 정점 하나는 두 자식 부분 트리의 승자끼리 치르는 경기 한 판을 뜻하고, 루트에서 이긴 선수가 금메달을 받는다. 트리의 높이는 루트에서 잎까지 내려가는 경로에 놓인 경기 수의 최댓값이며, 잎이 $N$개인 이진 트리가 가질 수 있는 최솟값 $\lceil \log_2 N \rceil$이어야 한다. 어떤 경기에서 두 부분 트리를 통째로 맞바꾼 대진표는 원래 대진표와 같은 것으로 센다.

입력은 여러 개의 데이터 세트로 이루어진다. 각 데이터 세트의 형식은 다음과 같다.

N M
R11 R12 ... R1N
R21 R22 ... R2N
...
RN1 RN2 ... RNN

$N$은 선수의 수이고 $2 \le N \le 16$이다. $M$은 친구의 번호이고 $1 \le M \le N$이다. 선수 번호는 1번부터 매긴다. $R_{ij}$는 $i$번 선수와 $j$번 선수가 붙었을 때의 결과다. $i$번 선수가 항상 이기면 $R_{ij} = 1$, 아니면 $R_{ij} = 0$이다. 행렬에는 모순이 없다. $i \ne j$인 모든 쌍에서 $R_{ij} = 0$인 것과 $R_{ji} = 1$인 것은 서로 같은 뜻이다. 대각 원소 $R_{ii}$는 편의를 위해 주어지고 값은 항상 0이다.

입력의 끝은 0 두 개가 적힌 줄로 알린다. 이 줄은 데이터 세트가 아니므로 처리하지 않는다.

각 데이터 세트마다 친구가 우승하는 대진표의 개수를 한 줄에 출력한다.