CSES - HIIT Open 2019 - Grid Paths
• Time limit: 1.00 s
• Memory limit: 512 MB
Given a grid of $n \times n$ numbers, consider paths from the top-left square to the bottom-right square where you move right or down on each step.

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$
Example 1

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