题目描述

As walking down the stairs of the literally Tower of White Jade, Youmu can't stop thinking about the determinant which she learned on the books as her leisure time.

Now, Youmu just wants to write a program on how to calculate the determinant, but now she has arrived at the end of the stairs of the literally Tower of White Jade and is about to leave the Netherworld. So she has no time to do that, can you write a program for calculating the determinant for her?

As the answer may be quite huge, please modular the answer 20210213.

输入格式

The first line of the input contains one positive integer $n (2\\le n\\le10)$ indicating the order of the determinant.

Then follows $n \ imes n$ sizes of positive integers $a[i][j] (-10^9\\le a[i][j]\\le10^9)$indicating the number in the determinant.

输出格式

The answer $det(A)$

样例

2 
4 5 
1 9

31

4 
1 4 -1 4 
2 1 4 3 
4 2 3 11 
3 0 9 2 

10

2 
4 5 
-1 -9

20210182

提示

The determinant is a scalar value that can be computed from the elements of a square matrix and encodes certain properties of the linear transformation described by the matrix. The determinant of a matrix A is denoted det(A)​, det A, or |A|. Geometrically, it can be viewed as the volume scaling factor of the linear transformation described by the matrix. This is also the signed volume of the n-dimensional parallelepiped spanned by the column or row vectors of the matrix. The determinant is positive or negative according to whether the linear transformation preserves or reverses the orientation of a real vector space.

In the case of a 2 × 2 matrix the determinant may be defined as

Similarly, for a 3 × 3 matrix A, its determinant is

The determinant of a matrix of arbitrary size can be defined by the Leibniz formula or the Laplace formula.

The Leibniz formula for the determinant of an n × n matrix A is

Here the sum is computed over all permutations σ of the set {1, 2, ..., n}. A permutation is a function that reorders this set of integers. The value in the ith position after the reordering σ is denoted by σ**i. For example, for n = 3, the original sequence 1, 2, 3 might be reordered to σ = [2, 3, 1], with σ1 = 2, σ2 = 3, and σ3 = 1. The set of all such permutations (also known as the symmetric group on n elements) is denoted by Sn. For each permutation σ, sgn(σ) denotes the signature of σ, a value that is +1 whenever the reordering given by σ can be achieved by successively interchanging two entries an even number of times, and −1 whenever it can be achieved by an odd number of such interchanges.

In any of the $n!$ summands, the term

is notation for the product of the entries at positions (i, σi), where i ranges from 1 to n:

For example, the determinant of a 3 × 3 matrix A (n = 3) is