题目描述

对于数组 $A=[a_1,a_2,\ldots,a_n]$，定义其最大子段和为

$$\operatorname{MSS}(A)= \max_{1\le i\le j\le n}\left(\sum_{k=i}^{j}a_k\right).$$

给定一个 $N\times N$ 的整数矩阵。你从单元格 $(1,1)$ 出发，每一步只能向右或向下移动，直到到达 $(N,N)$。把沿途经过的 $2N-1$ 个单元格中的数按访问顺序写成序列。

请计算有多少条不同的路径，使所得序列的最大子段和恰好等于 $K$。

两种方案不同，当且仅当它们在矩阵上的路径不同。

输入格式

第一行包含两个整数 $N,K$。

接下来 $N$ 行，每行包含 $N$ 个整数；第 $i$ 行第 $j$ 个数为 $A_{i,j}$。

数据范围：

$$1\le N\le 20,$$ $$-4\times 10^{10}\le K\le 4\times 10^{10},$$ $$-10^9\le A_{i,j}\le 10^9.$$

输出格式

输出最大子段和恰好为 $K$ 的路径数量。

样例 1

输入

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

输出

2

样例 2

输入

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

输出

4

样例说明

样例 1 中共有六条路径，对应序列为：

[1, 2, -5, 0, 1]
[1, 2, 3, 0, 1]
[1, 2, 3, -1, 1]
[1, -2, 3, 0, 1]
[1, -2, 3, -1, 1]
[1, -2, -1, -1, 1]

其中只有第一个与第五个序列的最大子段和为 $3$。