### 问题描述 Alice 拥有一批货物，数量为 $n$，货物的价值用数组 $a$ 来表示，第 $i$ 个货物的价值为 $a_i$。现在 Alice 想要出售这批货物，出售价格为所有货物的价值总和。 在 Alice 刚要出手之际，她被魔法师 Bob 阻止了。Bob 表示他有一个魔法，能够提升货物的售价。 假设一批货物价值用数组 $c$ 来表示，经由 Bob 的魔法会变成数组 $b$，具体规则如下： $$ \begin{cases} b_i = c_i, i=1 \\\\ b_i = max(b_{i-1}, c_i), i > 1 \end{cases} $$ 但是 Bob 并不能白白为 Alice 施展魔法，所以他向 Alice 提出了一个问题作为考验：对于 $a$ 的所有子数组，经由 Bob 施展魔法后的出售价格总和是多少。由于数量实在太大，你只需要告诉 Bob 答案对 $1000000007$ 取模的结果。 $a$ 的子数组是 $a$ 的一段连续部分，对于所有的 $1 \le i \le j \le n$，$a_i,a_{i+1},...,a_j$ 是 $a$ 的子数组。 Alice 无法解决这道问题，你能帮帮她吗？ ### 输入格式 第 $1$ 行输入一个整数 $n$，表示 Alice 货物的数量。 第 $2$ 行输入 $n$ 个整数，第 $i$ 个整数代表第 $i$ 个货物的价值 $a_i$。 ### 输出格式 输出一行，这一行只包含一个整数，表示 $a$ 的所有子数组经由 Bob 施展魔法后的出售价格总和对 $1000000007$ 取模的结果。 ### 样例输入 ``` 3 3 7 5 ``` ### 样例输出 ``` 56 ``` ### 样例说明 样例的子数组以及对应 $b$ 数组情况如下： $3$ 的 $b$ 数组为 $3$。贡献为 $3$。 $7$ 的 $b$ 数组为 $7$。贡献为 $7$。 $5$ 的 $b$ 数组为 $5$。贡献为 $5$。 $3,7$ 的 $b$ 数组为 $3,7$。贡献为 $10$。 $7,5$ 的 $b$ 数组为 $7,7$。贡献为 $14$。 $3,7,5$ 的 $b$ 数组为 $3,7,7$。贡献为 $17$。 结果为 $(3+7+5+10+14+17) \space mod \space 1000000007 =56$。 ### 数据范围 对于 $50\\%$ 的评测数据，$1 \le n \le 500$，$1 \le a_i \le 10^9$。 对于所有评测数据，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。