Moduic Squares
시간 제한8초메모리 제한512 MB
3×3 마방진에 나머지 값을 정하는 칸 하나를 더한 모듀익 정사각형이 일부 채워져 있을 때, 1부터 10까지의 수로 빈칸을 채워 모든 행, 열, 대각선 합이 J로 나눈 나머지가 같아지는 경우의 수를 센다.
문제
Have you ever heard of Moduic Squares? They are like 3 × 3 Magic Squares, but each of them has one extra cell called a moduic cell. Hence a Moduic Square has the following form.
Figure 1: A Moduic Square
Each of cells labeled from A to J contains one number from 1 to 10, where no two cells contain the same number. The sums of three numbers in the same rows, in the same columns, and in the diagonals in the 3 × 3 cells must be congruent modulo the number in the moduic cell. Here is an example Moduic Square:
Figure 2: An example Moduic Square
You can easily see that all the sums are congruent to 0 modulo 5.
Now, we can consider interesting puzzles in which we complete Moduic Squares with partially filled cells. For example, we can complete the following square by filling 4 into the empty cell on the left and 9 on the right. Alternatively, we can also complete the square by filling 9 on the left and 4 on the right. So this puzzle has two possible solutions.
Figure 3: A Moduic Square as a puzzle
Your task is to write a program that determines the number of solutions for each given puzzle.
입력
The input contains multiple test cases. Each test case is specified on a single line made of 10 integers that represent cells A, B, C, D, E, F, G, H, I, and J as shown in the first figure of the problem statement. Positive integer means that the corresponding cell is already filled with the integer. Zero means that the corresponding cell is left empty.
The end of input is identified with a line containing ten of -1’s. This is not part of test cases.
출력
For each test case, output a single integer indicating the number of solutions on a line. There may be cases with no solutions, in which you should output 0 as the number.