给出一包含整点 $1 \sim n$ 的数轴和其上的 $m$ 条线段，第 $i$ 条线段的左右端点分别为 $l_i,r_i$。

现对数轴上的每个整点都进行一次染色，整点 $i$ 被染色的成功率为 $p_i$，不同整点被染色的成功率互相独立。

称一线段被染色，当且仅当该线段上的至少一点被染色；求所有线段都被染色的概率。

输入格式

第一行含一个正整数 $t$ $(1 \leq t \leq 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 = 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$。

输出格式

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

样例

输入

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

输出

625000005
375000003
1
48000001
625000005
0

提示

样例中各答案的真实值依次为 $5/8, 3/8, 1, 8/3125, 5/8, 0$。