Deokin 教授正在教授算法课程。在即将到来的期中考试中，他决定加入他在课堂上讲授的最大子段和（maximum subarray sum）问题，即以下问题：

• 给定数组 $A = [a_1, a_2, \dots, a_n]$，计算值 $MSS(A) = \max_{1 \le i \le j \le n} \left( \sum_{k=i}^j a_k \right)$。

Deokin 想要强迫学生们手动解决最大子段和问题。为此，他使用了以下步骤：

• 准备一个大小为 $N \times N$ 的二维整数数组。
• 从单元格 $(1, 1)$ 开始，重复向右或向下移动，直到到达单元格 $(N, N)$。如果当前单元格是 $(i, j)$，若 $j < N$ 他可以向右移动到单元格 $(i, j + 1)$，若 $i < N$ 他可以向下移动到单元格 $(i + 1, j)$。
• 写下一个长度为 $2N - 1$ 的序列，其中按访问顺序包含所经过单元格中的元素。

Deokin 教授想在题目中加入一个“内部梗”（inside joke），以便那些上课专心听讲的学生能对自己的答案充满信心。他希望构造一个序列，使得其 $MSS(A)$ 的值恰好为 $K$。给定一个大小为 $N \times N$ 的二维数组，你需要求出网格中共有多少条不同的路径，其对应的序列的最大子段和恰好为 $K$。

输入格式

第一行包含两个整数 $N$ 和 $K$，分别表示二维数组的大小和目标值（$1 \le N \le 20$，$-4 \times 10^{10} \le K \le 4 \times 10^{10}$）。

接下来的 $N$ 行，每行包含 $N$ 个整数，表示二维数组中的值。第 $i$ 行的第 $j$ 个整数表示值 $A_{i,j}$。数组中使用的所有下标均从 1 开始（$-10^9 \le A_{i,j} \le 10^9$）。

输出格式

输出一个整数，表示网格中能够产生最大子段和恰好为 $K$ 的序列的不同路径数量。

样例

输入样例 1

3 3
1 2 -5
-2 3 0
-1 -1 1

输出样例 1

2

输入样例 2

4 3
1 -1 1 1
1 1 1 1
1 1 1 1
1 1 -1 1

输出样例 2

4