Sudoku Variant

Time limit2sMemory limit512 MB

Summary

Given a 3x3 grid with at most three empty cells, count the ways to fill the empties so no digit repeats in any row or column.

Level: Easy3 of 10
Topics: Brute force, Backtracking, Implementation
Solved: No attempts yet

Problem

Sudoku is a famous logic puzzle game played on a 9x9 grid. The player fills the grid so that every row, column, and 3x3 box contains the digits 1 through 9. In this problem, you will work on a variant of this puzzle played on a 3x3 grid.

As in Sudoku, the 3x3 grid you are given is already partially filled with the digits 1 through 9. You must fill the remaining empty cells with the digits 1 through 9 so that the numbers appearing in every row and every column are distinct, that is, a number cannot be repeated along a row or a column.

The given grid has at least 1 and at most 3 empty cells, and the partially filled grid is consistent with the rules, so no number is duplicated in any row or column. Determine the number of ways the empty cells can be filled.

Input

The input consists of 3 lines of 3 digits each, with the digits separated by a single space. Each line gives 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. A digit from 1 through 9 in the input indicates that the cell is already filled with that digit, while the digit 0 indicates that the cell is empty.

Output

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

Examples3

Example 1
Input
```
1 2 3
2 0 1
3 1 2
```
Expected output
```
7
```
Example 2
Input
```
1 2 3
4 5 6
7 8 0
```
Expected output
```
5
```
Example 3
Input
```
9 8 0
8 5 9
7 9 0
```
Expected output
```
43
```