题目描述

共有 $N$ 名网球选手，编号为 $1\sim N$。任意两名选手之间的胜负关系是确定的。

给出矩阵 $R$：

• $R_{ij}=1$ 表示选手 $i$ 与选手 $j$ 比赛时，$i$ 一定获胜；
• $R_{ij}=0$ 表示 $i$ 不会战胜 $j$。

对于任意 $i\ne j$，保证恰有一人能战胜另一人。

现在要安排一棵单败淘汰赛树。每个叶子对应一名选手，每个内部结点表示它的两个子比赛胜者之间进行一场比赛。若两棵子树交换左右位置，不视为不同的比赛安排；也就是说，我们只关心配对层次，而不区分一场比赛的“左边”和“右边”。

比赛树的高度必须在所有包含 $N$ 名选手的合法二叉淘汰赛树中尽可能小，也就是最少需要 $\lceil\log_2N\rceil$ 轮；当 $N$ 不是 $2$ 的幂时，不同选手可能需要不同数量的实际比赛，相当于存在轮空。

给定你希望夺冠的选手 $M$，求有多少种最小高度的比赛安排能使 $M$ 最终夺冠。

输入格式

第一行两个整数 $N,M$。

接下来 $N$ 行，每行 $N$ 个整数，第 $i$ 行第 $j$ 个数为 $R_{ij}$。

保证：

• $1\le N\le16$；
• $1\le M\le N$；
• $R_{ii}=0$；
• 对任意 $i\ne j$，$R_{ij}=0$ 当且仅当 $R_{ji}=1$。

输出格式

输出一个整数，表示满足条件的比赛树数量。

样例

2 1
0 1
0 0

1

3 3
0 1 0
0 0 0
1 1 0

3

6 4
0 0 0 0 0 1
1 0 1 0 1 0
1 0 0 1 1 0
1 1 0 0 1 0
1 0 0 0 0 0
0 1 1 1 1 0

11