题目背景

题目提供者：Okami

朝田诗乃：一个优秀的长脖子鹿是会数数字的位数的。

题目描述

长颈鹿Abbi喜欢用脸滚键盘，它每次滚键盘就会把一段子区间的值乘起来。

定义子区间为一个区间中的一个连续区间。

定义一段子区间的权值为每个元素权值之积。

定义一段区间的期望权值为任意选出一段子区间的权值的期望值。

给定 $n$ 个数字，分别表示权值 $a_i$。

共 $q$ 次询问，对于一次询问 $l \ r$ 查询指定区间的期望权值。

输入格式

第一行，两个数 $n$ 和 $q$。

第二行 $n$ 个数，第 $n$ 个数表示序列初始值 $a_i$。

接下来 $q$ 行，每行两个数 $l \ \ r$，表示询问的区间。

输出格式

对于每次询问，输出指定区间的期望权值。

由于期望权值可以很大，请输出期望权值模 $100000007$。

不要问我除不尽怎么办了，看上面

还是不行的话请移步https://www.luogu.org/problem/P2613

5 3
6 12 6 3 27
1 1
4 5
1 3

6
37
100

提示

时空限制：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$.

建议使用读入优化。