**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