线段染色

Problem Description

给出一包含整点 $1 \sim n$ 的数轴和其上的 $m$ 条线段，第 $i$ 条线段的左右端点分别为 $l_i,r_i$ 。 现对数轴上的每个整点都进行一次染色，整点 $i$ 被染色的成功率为 $p_i$ ，不同整点被染色的成功率互相独立。 称一线段被染色，当且仅当该线段上的至少一点被染色；求所有线段都被染色的概率。

Input

第一行含一个正整数 $t ~ (1 \le t \le 5 \times 10^4)$ ，表示数据组数；接下来对于每组数据： 第一行包含 $2$ 个正整数 $ n,m ~ (1 \leq n \leq 2 \times 10^5,0 \leq m \leq 2 \times 10^5) $ ，表示数轴的长度和线段的个数； 第二行为序列 $a$ ，包含 $n$ 个整数，第 $i$ 个数 $a_i ~ (0 \leq a_i \leq 10)$ 代表整点 $i$ 被染色的成功率为 $p_i=\frac{a_i}{10}$； 接下来的 $m$ 行，每行包括 $2$ 个正整数，第 $i$ 行的两数依次代表第 $i$ 个线段的左右端点位置 $l_i,r_i ~ (1 \leq l_i \leq r_i \leq n)$ 。 保证 $\sum n,\sum m \leq 2.5 \times 10^6$ 。

Output

对于每组数据，输出一个非负整数独占一行，表示所有线段都被染色的概率对 $10^9+7$ 取模后的结果。

Sample Input

6
4 2
5 5 5 5
2 3
3 4
4 2
5 5 5 5
2 2
3 4
1 0
3
4 1
0 2 3 4
2 4
4 2
5 0 5 5
1 3
2 4
4 3
1 1 1 0
2 4
3 4
4 4

Sample Output

625000005
375000003
1
48000001
625000005
0

Hint

样例中各答案的真实值依次为 $ \frac{5}{8},\frac{3}{8},1,\frac{83}{125},\frac{5}{8},0 $ 。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（3）