문제 설명
세종이는 \(3 \times 3\) 빈칸 채우기 놀이를 하고 있다. \(3 \times 3\) 빈칸 채우기 놀이 방법은 아래와 같다.
예를 들어 \(k = 3\)일 때,
위와 같이 빈칸을 채운 경우 \(1~9\)까지 한번씩 사용했고 세로 합이 각각 15로, 최댓값과 최솟값의 차이가 0이므로 바르게 채운 경우이다.
위의 경우는 \(1~9\)까지 한 번씩 사용했고, 세로 합이 각 \(11, 19, 15\)로, 최댓값과 최솟값의 차이가 \(8\)이므로 바르게 채우지 못한 경우이다.
세종이는 빈칸이 있는 표가 주어질 때 가능한 경우의 수를 궁금해하고 있다. 세종이를 위해 가능한 경우의 수를 출력하는 프로그램을 만들어 도와주자.
- \(1\)부터 \(9\)까지의 수를 한 번씩 이용한다.
- 세로 합의 최댓값과 최솟값의 차가 k이하가 되도록 한다.
예를 들어 \(k = 3\)일 때,
| 1 | 4 | 7 |
| 8 | 2 | 5 |
| 6 | 9 | 3 |
위와 같이 빈칸을 채운 경우 \(1~9\)까지 한번씩 사용했고 세로 합이 각각 15로, 최댓값과 최솟값의 차이가 0이므로 바르게 채운 경우이다.
| 1 | 4 | 7 |
| 8 | 6 | 5 |
| 2 | 9 | 3 |
위의 경우는 \(1~9\)까지 한 번씩 사용했고, 세로 합이 각 \(11, 19, 15\)로, 최댓값과 최솟값의 차이가 \(8\)이므로 바르게 채우지 못한 경우이다.
세종이는 빈칸이 있는 표가 주어질 때 가능한 경우의 수를 궁금해하고 있다. 세종이를 위해 가능한 경우의 수를 출력하는 프로그램을 만들어 도와주자.
입력 설명
첫 번째 줄에는 \(k\)가 입력된다.
두 번째 줄부터 \(3 \times 3\)표에 있는 수가 공백을 기준으로 입력된다. 이 때 빈칸은 \(0\)으로 입력된다.
\((1 \le k \le 20)\)
두 번째 줄부터 \(3 \times 3\)표에 있는 수가 공백을 기준으로 입력된다. 이 때 빈칸은 \(0\)으로 입력된다.
\((1 \le k \le 20)\)
출력 설명
가능한 총 경우의 수를 출력한다. 가능한 경우가 없으면 0을 출력한다.
입력 예시 Copy
5
1 4 7
8 0 0
0 9 3
출력 예시 Copy
2