시험 문제 출제

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

• 배열 $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가 된다.