408441: GYM103118 K Piggy Calculator

Piggy is developing a fantastic calculator. This calculator innovatively invents a binary operator symbol that perfectly mixes addition and multiplication, which we call $$$\odot^k$$$ ($$$k$$$ is a positive integer).

The value of $$$a \odot^k b$$$ is equal to $$$(a + b) \times k$$$. The precedence between operators is that the higher the $$$k$$$, the higher the priority. The higher priority goes first. For example, $$$\odot^7$$$ has a higher priority than $$$\odot^6$$$, so you must calculate $$$\odot^7$$$ before $$$\odot^6$$$. The operators are left-associative. Between the operators with the same priority, you should calculate them from left to right. For example, in the expression $$$1 \odot^1 2 \odot^1 3$$$, you must calculate $$$1 \odot^1 2$$$ firstly.

Now, Piggy wants to ask you to help him implement a function. There is an expression with $$$n$$$ numbers and $$$n - 1$$$ $$$\odot^k$$$ operators. At the same time, there are $$$q$$$ queries, each of them shaped as $$$(L, R)$$$ $$$(1 \le L \le R \le n)$$$. You need to calculate the result of the sub-expression formed by the $$$L$$$-th number to the $$$R$$$-th number.

The first line contains one positive integer $$$n$$$ $$$(2 \le n \le 3 \cdot 10^5)$$$ – the length of the expression.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le i \le n, 1 \le a_i \le 10^6)$$$ – the $$$n$$$ numbers from left to right in the expression.

The third line contains $$$n-1$$$ positive integers $$$k_1, k_2, \dots, k_{n-1}$$$ $$$(1 \le i \le n - 1, 1 \le k_i \le 10^6)$$$, where the $$$i$$$-th operator from left to right is $$$\odot^{k_i}$$$ and is between the $$$i$$$-th number and the $$$i+1$$$-th number.

The forth line contains one positive integer $$$q$$$ $$$(1 \le q \le 3 \cdot 10^5)$$$ – the number of queris.

The next $$$q$$$ lines describe the queries, where the $$$i$$$-th line contains two integers $$$L_i, R_i$$$ $$$(1 \le L_i \le R_i \le n)$$$ that denote a query $$$(L_i, R_i)$$$.

For each query, print an integer in one line – the result of the calculation. Since the answer may be very large, you only need to print the answer modulo $$$10^9+7$$$.

5
1 2 3 4 5
5 2 3 4
2
1 5
2 4

264
46

In the first query, the equation is $$$1 \odot^5 2 \odot^2 3 \odot^3 4 \odot^4 5 = 15 \odot^2 3 \odot^3 4 \odot^4 5 = 15 \odot^2 3 \odot^3 36 = 15 \odot^2 117 = 264$$$.

In the second query, the equation is $$$2 \odot^2 3 \odot^3 4 = 2 \odot^2 21 = 46$$$.