aquilla

Se dă un șir de $N$ perechi de numere naturale $(d_i, v_i)$, pentru $i$ de la $1$ la $N$.

Un subșir de indici $1 \leq i_1 < i_2 < \cdots < i_k \leq N$ se numește șmecher dacă pentru oricare doi indici consecutivi $i_p$ și $i_{p+1}$ (pentru orice $1 \leq p < k$) din acest subșir, diferența $i_{p+1} - i_p$ este divizibilă cu $\min(d_{i_p}, d_{i_{p+1}})$.

Cerință

Să se determine suma produselor $v_{i_1} \times v_{i_2} \times \cdots \times v_{i_k}$ pentru toate subșirurile șmechere nevide, modulo $10^9 + 7$.

Date de intrare

Fișierul de intrare aquilla.in conține pe prima linie numărul natural $N$. Pe a doua linie se află $N$ numere naturale $d_1, d_2, \dots, d_N$, separate prin câte un spațiu. Pe a treia linie se află $N$ numere naturale $v_1, v_2, \dots, v_N$, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire aquilla.out va conține pe o singură linie un număr natural, reprezentând suma produselor tuturor subșirurilor șmechere nevide, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq d_i, v_i \leq 1 \ 000 \ 000 \ 000$;
• Tribunele Aquilla aprobă această problemă.

Exemplu

aquilla.in

3
2 3 2
1 10 100

aquilla.out

211

Explicații

Avem $N = 3$ perechi: $(2, 1)$, $(3, 10)$ și $(2, 100)$. Să analizăm toate subșirurile de indici posibile și nevide:

$(1)$: Valid prin definiție (un singur element). Produsul este $v_1 = 1$.

$(2)$: Valid. Produsul este $v_2 = 10$.

$(3)$: Valid. Produsul este $v_3 = 100$.

$(1, 2)$: Diferența indicilor este $2 - 1 = 1$. $\min(d_1, d_2) = \min(2, 3) = 2$. Deoarece $1$ nu este divizibil cu $2$, acest subșir nu este șmecher.

$(2, 3)$: Diferența indicilor este $3 - 2 = 1$. $\min(d_2, d_3) = \min(3, 2) = 2$. Deoarece $1$ nu este divizibil cu $2$, acest subșir nu este șmecher.

$(1, 3)$: Diferența indicilor este $3 - 1 = 2$. $\min(d_1, d_3) = \min(2, 2) = 2$. Deoarece $2$ este divizibil cu $2$, subșirul este șmecher. Produsul este $v_1 \cdot v_3 = 1 \cdot 100 = 100$.

$(1, 2, 3)$: Deoarece perechile adiacente $(1, 2)$ și $(2, 3)$ nu respectă condiția, subșirul nu este șmecher.

Suma produselor tuturor subșirurilor șmechere este: $1 + 10 + 100 + 100 = 211$. $211 \pmod{10^9 + 7} = 211$.