Nice Array

Time limit2sMemory limit512 MB

Summary

Count ways to fill the erased cells of an N by N array so that every permutation's diagonal sum is equal, modulo 1e9+7.

Level: Hard8 of 10
Topics: Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

You are given an $N \times N$ array $A$ and a permutation $P$ of the integers from $0$ to $N-1$ .

$\mathrm{Sum}(A, P) = A[0][P[0]] + A[1][P[1]] + \cdots + A[N-1][P[N-1]]$

An array is nice if $\mathrm{Sum}(A, P)$ is the same no matter which permutation $P$ you pick.

Some cells of $A$ have been erased. Write a program that counts the ways to fill in every erased cell so that the array is nice. Two ways are different if the finished arrays differ in at least one cell.

Input

The first line has the size $N$ ( $1 \le N \le 50$ ) of the array $A$ .

Each of the next $N$ lines has one row of $A$ as $N$ characters with no spaces. An erased cell is -, and every other cell is an integer between $0$ and $9$ .

Output

Print the number of ways to make the array nice, modulo 1,000,000,007, on the first line.

A number you fill in is an integer that is at least $0$ , and it may be larger than $9$ . No input has an infinite number of ways.

Examples6

Example 1
Input
```
2
1-
-2
```
Expected output
```
4
```
Example 2
Input
```
3
123
4--
--9
```
Expected output
```
1
```
Example 3
Input
```
3
9--
-9-
--9
```
Expected output
```
271
```
Example 4
Input
```
2
11
12
```
Expected output
```
0
```
Example 5
Input
```
4
-4--
-0-2
--1-
4---
```
Expected output
```
10
```
Example 6
Input
```
3
--2
02-
-10
```
Expected output
```
0
```