该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

抽奖(draw)

题目背景

在你的帮助下 $\text{uuku}$ 成功获得了这次知识大赛的总冠军。

但坑人的主办方决定用抽奖的方式发放奖品——星球。

题目描述

抽奖规则是这样的：

一共有 $n$ 个星球，第 $i$ 个星球有一个价值 $a_i$。

将由选手选出一个抽奖区间，记为 $[l,r]$。

接下来主办方将在 $[l,r]$ 中随机选取两个数（两次选取互不干扰）记为 $x,y$。

而选手将获得编号在 $[\min(x,y),\max(x,y)]$ 之中的星球。

$\text{uuku}$ 希望聪明的你告诉他，如果他选取的区间为 $[l,r]$ 那么他获得的星球总价值的所有情况的和是多少。

即 $\sum\limits_{i=\min(x,y)}^{\max(x,y)} a_i$ 的和是多少 (对于所有 $x,y$ 组合)。

$\text{uuku}$ 一共会问你 $m$ 次。

注意：

由于答案过大请对 $10^9+7$ 取余。

为了减少输出时间请输出 $m$ 次询问的和对 $10^9+7$ 的余数。

为了减少读入时间本题由数据生成器生成数据，具体格式见 $\text{sample.cpp}$。

输入格式

第一行三个整数，$n,m,sd$。

输出格式

共一行一个整数表示最终答案。

输入输出样例 #1

输入 #1

10 2 10

输出 #1

330468653

输入输出样例 #2

输入 #2

50000 5000 1236998

输出 #2

137944585

输入输出样例 #3

输入 #3

100000 100000 124701

输出 #3

608177768

说明/提示

样例1解释

具体数据如下:

646587008 172788309 748409565 431728518 891360240 964941590 694380241 566875052 705025035 813088567
8 8
2 3

两次答案如下:

$566875052$

$763593608$

对于询问 2, 一共有四种情况.

$(2,2):172788309$, $(3,3):748409565$, $(2,3),(3,2):172788309+748409565=921197874$.

总和为 $172788309+748409565+921197874\times 2 = 2763593622\equiv 763593608 \pmod {10^9+7}$.

数据范围

对于 $20\%$ 的数据，$1 \le n,m \le 500$。

对于 $40\%$的数据，$1 \le n,m \le 5 \times 10^3$。

对于 $60\%$的数据，$1 \le n,m \le 10^5$。

对于 $80\%$的数据，$1 \le n,m \le 10^6$。

对于 $100\%$ 的数据，$1 \le l \le r \le n,m \le 5 \times 10^6 ,1 \le a_i \le 10^9$。