暂无测试数据。

蒜头君的班级有 $n$ 个人，编号为 $1 \sim n$ ，他们要排队接水，第 $i$ 个人需要接 $t_i$ 秒，这样一个人需要等前边所有人接完水才能去接，他所花的时间就是从第一个接水的人到自己所有人接水时间的和，换人时间忽略不计。

如果让他们都排在一个水龙头处接水，那大家所花的时间就太长了，于是蒜头君想让编号连续的一部分人在这个水龙头这里接水，其他人去别的地方另行安排。

他会问你 $q$ 次询问，每一次会问，如果他只让编号为 $l$ 到 $r$ 的人在这里接水，这些接水的人花费的总时间是多少。

输入格式

输入第一行，包含一个正整数 $n(1 \leq n \leq 10 ^ 5)$ ，表示蒜头君的班级的人数。

接下来一行，包含 $n$ 个正整数 $t_i$ ，表示每个人接水的时间。

接下来一行，包含一个正整数 $q(1 \leq q \leq 10 ^ 5)$ ，表示询问的次数。

接下来 $q$ 行，每行两个正整数 $l_i, r_i(1 \leq l_i \leq r_i \leq n)$ ，表示这一次询问的区间。

输出格式

由于每次询问的答案都可能比较大，而且询问量较大，最后只需要输出一行，包含一个整数，表示 $q$ 次询问结果的总和对 $10 ^ 9 + 7$ 取模的结果。

数据范围

对于 $30\%$ 的数据， $1 \leq n, q \leq 10 ^ 2, 1 \leq t \leq 10 ^ 3$ 。

对于 $60\%$ 的数据， $1 \leq n, q \leq 5 \times 10 ^ 3, 1 \leq t \leq 10 ^ 6$

对于 $100\%$ 的数据，$1 \leq n, q \leq 10 ^ 5, 1 \leq t \leq 10 ^ 9$

5
1 3 5 4 2
2
1 3
2 5

51