시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB44342482.759%

문제

Sudoku is a famous logic puzzle game that is played on a 9x9 grid. In it, the player is required to fill in the grid so that every row, column and 3x3 box contains the digits 1 through 9. In this problem, you will be working on a variant of this puzzle which is played on a 3x3 grid.

Similar to Sudoku, the 3x3 grid you are given is already partially filled with the digits 1 through 9. Your job is to fill in the remaining empty grid positions with the digits 1 through 9 such that the numbers that appear in every row and every column are distinct, i.e. a number cannot be repeated along a row or column.

In the given grid there are at least 1 empty grid position and at most 3 empty grid positions, you may assume that the partially filled grid is consistent with the rules, i.e. no number is duplicated on any row or column. You are required to determine the number of ways the empty positions can be filled.

입력

The input consists of 3 lines of 3 digits each, the digits are separated by a single space. Each line contains the configuration of one row of the 3x3 grid. The first line represents the first row of the grid; the second line represents the second row and so on. The digit 1 through 9 in the input indicates that the particular grid position is already filled with the digit while the digit 0 indicates that the particular position is empty

출력

Output the number of ways in which the given puzzle can be solved.

예제 입력 1

1 2 3
2 0 1
3 1 2

예제 출력 1

7

예제 입력 2

1 2 3
4 5 6
7 8 0

예제 출력 2

5

예제 입력 3

9 8 0
8 5 9
7 9 0

예제 출력 3

43