127. Latin Squares
time limit per test
8 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A latin square is defined as a 4 by 4 grid of numbers, where all of the numbers in each row and column are distinct, i.e. no two pairs of elements in each row and column are equal.

You're given a partially filled in latin square. Figure out how many valid latin squares can be formed by filling in the empty digits of the latin square.

Input

The input consists of 4 lines, each consisting of 4 integers: the digits in the latin square. For each digit, if it has already been filled in, it will be represented with a digit from 1 to 4, and if it hasn't been filled in yet, it will be represented with a "0".

Output

Output a single positive integer $$$n$$$: the number of ways to fill in the latin square as described above.

Examples
Input
0000
0000
0000
0000
Output
576
Input
1234
2341
3412
0000
Output
1
Input
1234
2341
3412
4311
Output
0