RoAlgo Contest #11 - Back to School 2024 | Crocks

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 64MB Input: Output:

Task

You are given an array aa of NN elements.
The cost of a continuous subarray [st,dr][st, dr] is defined as C(st,dr)=ast(ast+1+ast+2++adr1)adrC(st, dr) = a_{st} \cdot (a_{st+1} + a_{st+2} + \dots + a_{dr-1}) \cdot a_{dr}.

You need to calculate st=1n2dr=st+2nC(st,dr)\sum_{st=1}^{n-2} \sum_{dr=st+2}^n C(st, dr) modulo 109+710^9+7.

Input data

The first line contains NN and the second line contains NN values representing the array aa.

Output data

A single number, the required sum modulo 109+710^9+7.

Constraints and clarifications

  • 1N1061 \leq N \leq 10^6
  • 1ai1091 \leq a_{i} \leq 10^9
  • For 2020 points, 1N1501 \leq N \leq 150.
  • For an additional 3030 points, 1N5 0001 \leq N \leq 5\ 000.

Example 1

stdin

4
2 1 3 2

stdout

28

Explanation

C(1,3)=6C(1, 3) = 6

C(1,4)=16C(1, 4) = 16

C(2,4)=6C(2, 4) = 6

Example 2

stdin

8
7 45 12 4398 183 13261 423871 321

stdout

235372600

Log in or sign up to be able to send submissions!