JOIN
Get Time

   Problem Statement  

 Problem Statement for EqualSums

Problem Statement

    Let A be a matrix with N rows and N columns and P be a permutation of integers from 0 to N-1. Consider the following sum: Sum(A, P) = A[0, P[0]] + A[1, P[1]] + ... + A[N-1, P[N-1]], where A[i, j] is the element of A in row i and column j (all indices in this problem are 0-based). The matrix A is called nice if Sum(A, P) is always equal to the same value disregarding of the choice of permutation P.



Fox Ciel wants to draw a nice matrix on the blackboard. She is given a String[] board. It contains N elements and each element contains N characters. If j-th character of board[i] is a digit '0', '1', '2', ..., '9', then A[i, j] must be equal to this digit. If j-th character of board[i] is '-', then A[i, j] can be equal to any non-negative integer (it is allowed to be greater than 9).



Let T be the number of different matrices that satisfy all Ciel's requirements (the constraints will guarantee that the number of such matrices is finite). Compute and return the value of (T modulo 1,000,000,007).
 

Definition

    
Class:EqualSums
Method:count
Parameters:String[]
Returns:int
Method signature:int count(String[] board)
(be sure your method is public)
    
 

Constraints

-board will contain between 1 and 50 elements, inclusive.
-Each element of board will contain exactly N characters, where N is the number of elements in board.
-Each character in board will be one of '-', '0', '1', '2', ..., '9'.
-The number of matrices that satisfy all Ciel's requirements will be finite.
 

Examples

0)
    
{"1-",
 "-2"}
Returns: 4
The sum A[0, 1] + A[1, 0] must be equal to 3.
1)
    
{"123",
 "4--",
 "--9"}
Returns: 1
2)
    
{"9--",
 "-9-",
 "--9"}
Returns: 271
3)
    
{"11",
 "12"}
Returns: 0
There are no nice matrices that match the given board, so T = 0.
4)
    
{"-4--",
 "-0-2",
 "--1-",
 "4---"}
Returns: 10
5)
    
{"--2",
 "02-",
 "-10"}
Returns: 0
6)
    
{"----------1---------------0-----7-----------------",
 "-----4--------------------------------------------",
 "--------5-------------5-3---5---------------6-----",
 "-------2----------1-------------------------------",
 "-----4--------------------------------------------",
 "-----3--------------------------------------------",
 "-6----------5-------------------------------------",
 "-------------------------------7---5----------6---",
 "--------6-------------6-4---6---------------7-----",
 "-------------4----------------5-------------------",
 "3------------------------------------------6------",
 "3------------------------------------------6------",
 "-------------4----------------5-------------------",
 "---------------2-------------------------3--------",
 "--2------------------------------------------2----",
 "---8---------------1-------------------3----------",
 "---------------3----------------------------------",
 "----7----------------5---0-----------------------5",
 "----------------5-------------------------3-----1-",
 "----------1---------------0-----7-----------------",
 "-------------5----------------6-------------------",
 "-7----------6-------------------------------------",
 "---8---------------1-------------------3----------",
 "-----------------------3--------------------------",
 "----8----------------6---1-----------------------6",
 "------------------------------------------4-----2-",
 "-----------5---------------5----------------------",
 "-----------------------------6--------------------",
 "----8----------------6---1-----------------------6",
 "----------------5-------------------------3-----1-",
 "-------------------------------6---4--2-------5---",
 "-6----------5-------------------------------------",
 "--------5-------------5-3---5---------------6-----",
 "-------------5----------------6-------------------",
 "-----3--------------------------------------------",
 "---------------2-------------------------3--------",
 "---------4---------------------------6------------",
 "-------------------------------6---4--2-------5---",
 "------2-------------1------------22---------------",
 "--------5-------------5-3---5---------------6-----",
 "-----------5--3------------5----------------------",
 "--2------------------------------------------2----",
 "---------5---------------------------7------------",
 "-------------4----------------5-------------------",
 "-----------------5------------------4---6------2--",
 "-------------------------------6---4--2-------5---",
 "-----------------------2--------------------------",
 "----------------6-------------------------4-----2-", 
 "-------------------------------6---4--2-------5---",
 "--------5-------------5-3---5---------------6-----"}
Returns: 45094393

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 568 Round 1 - Division I, Level Two