Domino Game 2

Each domino contains an ordered pair of numbers.

Sejun has one domino for every ordered pair (i, j). Here 1 <= i <= N and 1 <= j <= N, so there are N^2 dominoes in total.

In the game, the dominoes are placed on an N x N board. The cell in row i and column j contains the domino labeled (i, j).

The player must choose exactly N dominoes. No two chosen dominoes may come from the same row, and no two chosen dominoes may come from the same column.

The chosen dominoes split into one or more cycle groups. If the second number of domino A equals the first number of domino B, then B can follow A; if the second number of the last domino equals the first number of the first domino, those dominoes form a cycle. A domino such as (i, i) forms a one-domino cycle group by itself.

Because exactly one domino is chosen from each row and each column, every valid choice always splits into one or more cycle groups.

Every domino also has one number written on its back. The score of a choice is the product of the back-side numbers of all chosen dominoes. If the number of cycle groups in that choice is even, multiply the score by -1 once more.

Given the numbers written on the backs of the dominoes, compute the sum of scores over all valid choices.

The first line contains a positive integer N. N is at most 100.

The next N lines describe the numbers written on the backs of the dominoes. The j-th character of the i-th line is the number on the back of domino (i, j).

Each character is either a digit from 0 to 9 or an uppercase letter from A to I. The letters A through I mean -1 through -9, respectively.

Print the sum of all possible scores modulo 121547.