시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)80474381.132%

문제

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

  • 배열 $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

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

노트

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

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