Description

假设市井中的摊位排布在一条直线上，共有 $n$ 个摊位，其中第 $i$ 个摊位的坐标是$x_i$，这 $n$ 个点的位置互不相同且构成一个连续的整数集合(把这个集合中的数字从小到大排序后，满足后一个数值等于前一个数值+1).每个摊位初始的分数值都是0. 接下来有 $m$ 次事件发生，每次事件给出一对整数 $l,r$，对于 $\forall i \in [1,n]$, 若 $l\le x_i \le r$, 则本次操作该点分数值不变，否则该点分数值加 1。 现在需要专诸计算，在 $m$ 次事件之后，所有摊位的分数总和是多少？由于结果可能很大，请输出其对 10007 取模后的结果。

Format

Input

第一行两个整数n,m($1 \le n,m \le 3\times 10^5$)。

第二行n个整数 $x_1 \sim x_n(1 \le x_i \le 10^9)$。

接下来m行，每行两个整数l,r($1 \le l \le r \le 10^9$).

Output

一个整数表示操作结束后所有点的分数值之和对10007取模的结果。

Samples

5 2
3 5 4 7 6
4 100
1 3

5