- Time limit: 1.00 s
- Memory limit: 512 MB
Given a grid of 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 : the size of the grid.
Then, there are lines that describe the grid. Each line consists of integers.
Output
Print one integer: the sum of numbers in the paths modulo .
Constraints
- each number if between
Example 1
Input:
2 3 4 5 1
Output:
17
Explanation: There are two paths whose sums are and , so the total sum is .
Example 2
Input:
3 1 2 3 4 5 6 7 8 9
Output:
150