P5498 [LnOI2019] 脸滚键盘

题目提供者：Okami 朝田诗乃：一个优秀的长脖子鹿是会数数字的位数的。

长颈鹿Abbi喜欢用脸滚键盘，它每次滚键盘就会把一段子区间的值乘起来。 定义子区间为一个区间中的一个连续区间。 定义一段子区间的权值为每个元素权值之积。 定义一段区间的期望权值为任意选出一段子区间的权值的期望值。 给定 $n$ 个数字，分别表示权值 $a_i$。 共 $q$ 次询问，对于一次询问 $l \ r$ 查询指定区间的期望权值。

第一行，两个数 $n$ 和 $q$。 第二行 $n$ 个数，第 $n$ 个数表示序列初始值 $a_i$。 接下来 $q$ 行，每行两个数 $l \ \ r$，表示询问的区间。

对于每次询问，输出指定区间的期望权值。 由于期望权值可以很大，**请输出期望权值模 $100000007$。** 不要问我除不尽怎么办了，看上面 还是不行的话请移步https://www.luogu.org/problem/P2613

时空限制：1s/512MB 对于30%的数据，$1 \leq n, q \leq 100$ 对于100%的数据，$1 \leq n, q \leq 10^6$，$1 \leq a_i \leq 10^7$ 样例解释：对于区间 $[1,1]$，共有一个子区间 $[1,1]$，权值为 $6$，每个区间取到的概率是 $\frac{1}{1}$，期望权值为6. 对于区间 $[4,5]$，共有三个子区间 $[4,4]$、$[4,5]$、$[5,5]$，权值分别为 $3$、$81$、$27$，每个区间取到的概率是 $\frac{1}{3}$，总期望权值为 $37$. 对于区间 $[1,3]$，共有个六子区间 $[1,1]$、$[1,2]$、$[1,3]$、$[2,2]$、$[2,3]$、$[3,3]$，权值分别为 $6$、$72$、$432$、$12$、$72$、$6$，每个区间取到的概率是 $\frac{1}{6}$，总期望权值为 $100$. 建议使用读入优化。