CSES - HIIT Open 2019 - Grid Paths
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Given a grid of n×nn \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 nn: the size of the grid.

Then, there are nn lines that describe the grid. Each line consists of nn integers.

Output

Print one integer: the sum of numbers in the paths modulo 109+710^9+7.

Constraints

  • 1n1001 \le n \le 100
  • each number if between 11091 \dots 10^9

Example 1

Input:

2
3 4
5 1

Output:

17

Explanation: There are two paths whose sums are 3+4+1=83+4+1=8 and 3+5+1=93+5+1=9, so the total sum is 8+9=178+9=17.

Example 2

Input:

3
1 2 3
4 5 6
7 8 9

Output:

150