题目描述

CDR 在超市排队，队伍实在是太长了，总共有 n 个人，但是她发现她可以根据每个人手里的东西来大致判断这个人需要花多少时间结账。 于是为了打发时间，CDR 给自己出了一个问题。

假设有 3 个人，结账需要花费的时间分别为 1,2,3。 每个人的排队时间是她的等待时间加上她自己结账的时间，所以这 3 个人的排队时间分别为 1,3,6

这三个人总的排队时间即为 1+3+6=10。

计算所有人的排队总时间实在是太简单了。 所以 CDR 想知道，如果单独选出其中第 l 个人到第 r 个人（包含这两个人)，把她们移到一个新的窗口去结账，所有人总的等待时间是多少？

P.S. 这里不考虑其她任何时间花费，例如移动等时间花费，都不考虑。

输入格式

输入第一行，包含一个正整数 n ，表示排队的总人数 接下来一行，包含 n 个正整数 ai，表示每个人结账需要花费的时间 接下来一行，包含一个正整数 q ，表示询问的次数。

接下来 q 行，每行两个正整数 l,r ，表示这一次的询问，含义如题。

无多组样例，其中1≤n,q≤10^5, 1≤ai≤10^9

输出格式

对于每个询问输出一行，表示询问的结果，因为答案可能较大，所以请将答案对 109+7 取模。

3
1 2 3
1 
1 3

10

提示

会不会爆int64呢？