题目描述

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 $10^9+7$.

picture: the stairs of the literally Tower of White Jade

输入格式

The first line of the input contains one positive integer $n (2\\le n\\le500)$ 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

999999976