시험 문제 출제

덕인 교수는 알고리즘 과목을 강의한다. 다가오는 중간고사 시험 문제를 준비하던 덕인 교수는 얼마 전 학생들에게 가르친 최대 부분합 문제를 추가하기로 했다. 최대 부분합 문제는 다음과 같다.

• 배열 $A=[a_1, a_2, \dots, a_n]$가 주어질 때, $\max_{1 \leq i \leq j \leq n}(\sum_{k=i}^{j}a_k)$를 구하여라.

덕인 교수는 수열 하나를 주고 그 수열의 최대 부분합을 구하도록 할 생각이다. 수열 제작의 대가인 덕인 교수는 다음과 같은 과정으로 수열을 만든다고 알려져 있다.

• 정수만으로 구성된 $N \times N$ 크기의 이차원 배열을 준비한다.
• $(1, 1)$에서 출발해 아래 혹은 오른쪽으로 이동하는 것을 반복하여 $(N, N)$에 도착한다. $(i, j)$에서 아래로 이동하면 $(i+1, j)$에 도달하고, 오른쪽으로 이동하면 $(i, j+1)$에 도달한다.
• 지나온 칸에 적힌 정수를 지나온 순서대로 나열하여 길이 $2N-1$의 수열을 완성한다.

덕인 교수는 '답이 $K$인 문제는 아름다운 문제'라는 신념을 가지고 있어서 최대 부분합이 $K$인 수열을 만들려고 한다. 여기에 더해서, 최대 부분합이 $K$인 수열을 최대한 많은 방법으로 만들려고 한다. 덕인 교수의 조교인 당신은 $N \times N$ 크기의 이차원 배열이 주어지면, 최대 부분합이 $K$인 수열을 만드는 서로 다른 방법의 수를 구해야 한다. 어떤 두 방법이 서로 다르다는 것은 두 수열을 구성하는 이차원 배열상의 경로가 서로 다르다는 것을 의미한다.

첫 번째 줄에는 이차원 배열의 크기 $N$과 만들고자 하는 최대 부분합 $K$가 주어진다. $(1 \leq N \leq 20, -4 \times 10^{10} \leq K \leq 4 \times 10^{10})$

그 다음 $N$개의 줄에 걸쳐 각 줄에 $N$개의 정수가 공백으로 구분되어 주어진다. 구체적으로, $i$번째 줄의 $j$번째 정수는 이차원 배열 $A$의 $(i, j)$에 위치하는 $A_{i,j}$를 의미한다. $(-10^9 \leq A_{i,j} \leq 10^9)$

주어진 배열에서 최대 부분합이 $K$인 수열을 만드는 서로 다른 방법의 수를 출력한다.

첫 번째 예제에서 만들 수 있는 수열들은 다음과 같다.

• $[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인 수열은 1번째와 5번째 수열뿐이므로 답으로 2를 출력한다.

두 번째 예제에서는 만들 수 있는 수열들 중 $[1, -1, 1, 1, 1, -1, 1]$만이 최대 부분합이 3이고, 이러한 수열을 만들기 위해서는 $(1, 2)$와 $(4, 3)$을 반드시 지나야 하므로 경우의 수는 4가 된다.