小红的环形数组
题号：NC255044
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红拿到了一个环形数组。她定义两个下标的贡献f(i,j)=(a_i+a_j)*dis(i,j)，其中dis(i,j)为下标i和下标j在数组中的距离。小红想知道，每一对下标的贡献之和是多少？
用数学语言描述，你需要求出\sum_{i=1}^n\sum_{j=i+1}^n f(i,j)的值，并对答案取模10^9+7。

输入描述:

第一行输入一个正整数n，代表环形数组的大小。
第二行输入n个正整数a_i，代表数组的元素。
1\leq n,a_i \leq 200000

输出描述:

一个正整数，代表\sum_{i=1}^n\sum_{j=i+1}^n f(i,j)的值。
示例1

输入

复制 
3
1 2 3

输出

复制 
12

说明

由于是环形数组，所以任意两个下标的距离都是 1，最终答案是 (1+2)*1+(2+3)*1+(1+3)*1=12