Hyobin's Tutoring

Interview

Time limit1sMemory limit512 MB

Summary

Multiply N matrices in the given order and print the sum of the product's entries modulo 1,000,000,007, or -1 if the shapes do not line up.

Level: Easy3 of 10
Topics: Implementation, Math, Array
Solved: No attempts yet

Problem

Youngwoo started studying matrices, but he could not get far on his own, so he asked Hyobin to tutor him. After testing him, Hyobin found that matrix multiplication is his weakest point and assigned matrix multiplication as homework. Youngwoo did not want to do the homework, so he asked you for a program that multiplies the matrices for him.

You are given $N$ matrices. Multiply all of them in the order given and compute the sum of the entries of the resulting matrix.

Input

Input is read from standard input. The first line contains the number of matrices $N$ . ( $1 \le N \le 100$ )

The $N$ matrices follow in the order in which they are multiplied. Each matrix begins with a line holding the number of rows $X$ and the number of columns $Y$ , separated by a space ( $1 \le X, Y \le 50$ ). The next $X$ lines each hold the $Y$ entries of one row, separated by spaces. Every entry is an integer between 1 and 100.

Output

Output is written to standard output. Print on one line the sum of all entries of the product of the $N$ matrices in the given order, taken modulo 1,000,000,007.

If the product cannot be formed, print -1 instead. The product cannot be formed when the number of columns of some matrix differs from the number of rows of the matrix right after it. When $N$ is 1, print the sum of the entries of that single matrix.

Examples2

Example 1
Input
```
2
1 2
1 1
2 2
5 6
7 8
```
Expected output
```
26
```
Example 2
Input
```
2
1 2
1 2
1 4
3 2 4 6
```
Expected output
```
-1
```