黄桃罐头

题目描述

有一排 $n$ 只奶龙并排在一起。每只奶龙身上有一个数字 $a_i$，数字标志着它能产生几瓶黄桃罐头。你可以选择两个奶龙，这两个奶龙之间（包括这两只奶龙）所有奶龙能产生的黄桃罐头之和称为该种选择的黄桃罐头数。

现在你想知道所有选择的黄桃罐头数之和对 $10^9+7$ 取模的结果。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个非负整数表示 $a_i$。

输出格式

一行一个整数，表示所有选择的黄桃罐头数之和对 $10^9+7$ 取模的结果。

样例

样例输入 #1

3
1 2 3

样例输出 #1

20

样例输入 #2

5
3 7 5 2 6

样例输出 #2

162

样例输入 #3

7
2 1 4 7 8 9 1

样例输出 #3

433

数据范围与约定

对于 $30\%$ 的数据，$1\leq n\leq 100$;

对于 $50\%$ 的数据，$1\leq n\leq 1000$;

对于 $100\%$ 的数据，$1\leq n\leq 100000,0\leq a_i\leq 50000$。