观测窗的缺测记录 (missing_observations)

题目描述

一条长为 $N$ 的观测带上有 $N$ 个采样点，第 $i$ 个采样点的读数为 $a_i$。研究员需要统计所有连续观测窗的读数总和。

不过设备日志里还有 $M$ 条缺测规则。每条规则形如 $x\ y$，表示：只要某个观测窗的左端点或右端点等于 $x$，那么在计算这个观测窗的总和时，采样点 $y$ 的读数不可使用。

如果同一个观测窗内，同一个采样点被多条规则要求不可使用，它也只会被删去一次。

对所有满足 $1 \le l \le r \le N$ 的连续区间 $[l,r]$，原本区间读数和为 [ \sum_{k=l}^{r} a_k ]

若存在规则 $(x,y)$，且 $l=x$ 或 $r=x$，则在该区间求和时不计入 $a_y$。当然，只有当 $y$ 位于区间 $[l,r]$ 内时，这条删除才会产生影响。

请计算所有区间结果之和对 $10^9+7$ 取模后的值。

输入格式

在文件 missing_observations.in 中读入。 第一行两个整数 $N$，$M$。 第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。 接下来 $M$ 行，每行两个整数 $x$，$y$，表示一条缺测规则。

输出格式

在文件 missing_observations.out 中输出。 输出一个整数，表示答案对 $10^9+7$ 取模后的值。

样例

输入数据1

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

输出数据1

69

提示

数据范围

• 对于10%的数据，$N,M \le 100$，$a_i \le 10$。
• 对于另一部分数据，$N,M \le 5000$，$a_i \le 10$。
• 另有20%的数据，$M=0$。
• 对于100%的数据，$1 \le N,M \le 10^6$，$1 \le a_i<10^9+7$，$1 \le x,y \le N$。
• 数据保证不会出现完全相同的规则。