- Prepare
- Algorithms
- Dynamic Programming
- Summing Pieces

# Summing Pieces

# Summing Pieces

Consider an array, , of length . We can split into contiguous segments called *pieces* and store them as another array, . For example, if , we have the following arrays of pieces:

- contains three -element pieces.
- contains two pieces, one having elements and the other having element.
- contains two pieces, one having element and the other having elements.
- contains one -element piece.

We consider the *value* of a piece in some array to be , and we consider the *total value* of some array to be the sum of the values for all pieces in that . For example, the total value of is .

Given , find the total values for all possible 's, sum them together, and print this sum modulo on a new line.

**Input Format**

The first line contains a single integer, , denoting the size of array .

The second line contains space-separated integers describing the respective values in (i.e., ).

**Constraints**

**Output Format**

Print a single integer denoting the sum of the total values for all piece arrays ('s) of , modulo .

**Sample Input 0**

```
3
1 3 6
```

**Sample Output 0**

```
73
```

**Explanation 0**

Given , our piece arrays are:

- , and .
- , and .
- , and .
- , and .

When we sum all the total values, we get . Thus, we print the result of on a new line.

**Sample Input 1**

```
5
4 2 9 10 1
```

**Sample Output 1**

```
971
```