[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

输入输出样例

输入样例 #1

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

输出样例 #1

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. 建议使用读入优化。