Win

世界乒乓球比赛马上要拉开帷幕，你被邀请成为组委会成员，并且负责安排比赛赛程。比赛采取淘汰赛赛制，失败的一方将被直接淘汰。

你手上现在有一份各个队员近期的战况，战况包含任意两名队员的最近一次交手结果。你默认这份对战结果将代表比赛的结果。

现在，你的好友要参加乒乓球比赛，你需要帮好友算一下，你可以安排出多少种淘汰赛赛程使得你的这位好友能够拿到最终的冠军。

当然，介于比赛的公平性，赛程的安排需要遵循这个原则：使得淘汰赛的赛程树高度最低，也就是说，使得每位选手打的比赛数尽量平均。

输入格式

本题为多组数据，请处理到文件结束。

每组数据第一行有两个整数 $N, M$。$N$ 表示总共有 $N$ 位选手参加比赛，$M$ 表示你的好友的编号。

接下来一个 $N\times N$ 的矩阵，表示选手两两间交手的胜负。其中第 $i$ 行、第 $j$ 列的数 $A_{i,j}$ 表示其胜负关系：$A_{i,j}$ 为 $1$ 表示 $i$ 胜过 $j$，$A_{i,j}$ 为 $0$ 表示 $i$ 输给过 $j$。

输出格式

每组数据输出一行，表示有多少种赛程安排可以使你的朋友拿到冠军。

样例输入

2 1
0 1
0 0
2 1
0 0
1 0
3 3
0 1 1
0 0 1
0 0 0

样例输出

1
0
0

样例解释

第一组数据中只有两位选手，好友是选手 $1$ 且他胜过选手 $2$，唯一的赛程就能让他夺冠，方案数为 $1$。

第二组数据中好友仍是选手 $1$，但他输给选手 $2$，无法夺冠，方案数为 $0$。

第三组数据中好友是选手 $3$，他对选手 $1$、$2$ 都是败绩，只要上场就会被淘汰，方案数为 $0$。

数据范围

• $2\le N\le 16$，$1\le M\le N$；
• $0\le A_{i,j}\le 1$，且 $A_{i,j}=1-A_{j,i}$，$A_{i,i}=0$。

来源与许可

本题题面与测试数据整理自 BZOJ 1399。

样例 1

输入

2 1
0 1
0 0
2 1
0 0
1 0
3 3
0 1 1
0 0 1
0 0 0

输出

1
0
0