题目描述

小 A 最近在研究一个简单的问题：有 $n$ 个数，其中第 $i$ 个数为 $a_i$，现在有 $m$ 段区间，其中第 $i$ 段区间左端点为 $l_i$，右端点为 $r_i$。现在要求这 $m$ 段区间上的数之和。也就是说要求：

现在他想让你帮他计算这个问题。结果对 $10^9+7$ 取模。

输入

第一行两个正整数 $n$ 和 $m$。 第二行 $n$ 个整数，其中第 $i$ 个整数表示 $a_i$。 接下来 $m$ 行，每行两个正整数 $l_i$ 和 $r_i$。

输出

一个整数，表示求得的和。

样例

5 3
1 4 2 3 3
1 3
2 3
1 5

26

数据规模

• $n\le10^6$
• $m\le10^6$
• $\left\vert a_i \right\vert \le10^9$，其中 $i\in[1,n]$
• $1\le l_i\le r_i \le n$，其中 $i\in[1,n]$