Aquilla

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 &le; i{~1~} < i{~2~} < ... < i{~k~} &le; N$ se numeşte _şmecher_ dacă pentru oricare doi indici consecutivi $i{~p~}$ şi $i{~p + 1~}$ (pentru orice $1 &le; p < k$) din acest subşir, diferenţa $i{~p + 1~} - i{~p~}$ este divizibilă cu $min(d{~{~i{~p~}~}~}, d{~{~i{~p + 1~}~}~})$.

Un subşir de indici $1 &le; i{~1~} < i{~2~} < ... < i{~k~} &le; N$ se numeşte _şmecher_ dacă pentru oricare doi indici consecutivi $i{~p~}$ şi $i{~p + 1~}$ (pentru orice $1 &le; p < k$) din acest subşir, diferenţa $i{~p + 1~} - i{~p~}$ este divizibilă cu _min_$(d{~{~i{~p~}~}~}, d{~{~i{~p + 1~}~}~})$.

h2. Cerinţă

Să se determine suma produselor $v{~i{~1~}~} *  v{~i{~2~}~} * ... * v{~i{~k~}~}$ pentru toate subşirurile _şmechere_ nevide, modulo $10^9^ + 7$.

Să se determine suma produselor $v{~i{~1~}~} *  v{~i{~2~}~} * ... * v{~i{~k~}~}$ pentru toate subşirurile _şmechere_ nevide, modulo 10^9^ + 7.

h2. 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~}, ..., d{~N~}$, separate prin câte un spaţiu. Pe a treia linie se află $N$ numere naturale $v{~1~}, v{~2~}, ..., v{~N~}$, separate prin câte un spaţiu.

Fişierul de intrare $aquilla.in$ ...

h2. 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$.

În fişierul de ieşire $aquilla.out$ ...

h2. Restricţii

* $1 ≤ N ≤ 200 000$
* $1 ≤ d{~i~}, v{~i~} ≤ 1 000 000 000$
* Tribunele Aquilla aprobă această problemă.
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $6$ | $N ≤ 20$|
| $2$ | $13$ | $N ≤ 2 000$|
| $3$ | $7$ | $N ≤ 200 000$ şi $d{~i~} = 1$ pentru orice $1 ≤ i ≤ N$|
| $4$ | $7$ | $N ≤ 200 000$ şi $1 ≤ d{~i~} ≤ 2$ pentru orice $1 ≤ i ≤ N$ |
| $5$ | $14$ |$N ≤ 200 000$ şi $1 ≤ d{~i~} ≤ 200$ pentru orice $1 ≤ i ≤ N$ |
| $6$ | $12$ | $N ≤ 100 000$ şi şirul $d$ este crescător |
| $7$ | $22$ | $N ≤ 100 000$  |
| $8$ | $19$ | Fără alte restricţii |

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. aquilla.in |_. aquilla.out |

| 3
2 3 2
1 10 100
| 211

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

* *(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~} * v{~3~} = 1 * 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 mod (10^9^ + 7) = 211$.

...

== include(page="template/taskfooter" task_id="aquilla") ==