- Time limit: 1.00 s
- Memory limit: 512 MB
What is the total sum of numbers in all such paths?
Input
The first input line has an integer $n$: the size of the grid.
Then, there are $n$ lines that describe the grid. Each line consists of $n$ integers.
Output
Print one integer: the sum of numbers in the paths modulo $10^9+7$.
Constraints
- $1 \le n \le 100$
- each number if between $1 \dots 10^9$
Input:
2
3 4
5 1
Output:
17
Explanation: There are two paths whose sums are $3+4+1=8$ and $3+5+1=9$, so the total sum is $8+9=17$.
Example 2
Input:
3
1 2 3
4 5 6
7 8 9
Output:
150