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 ≤ i{~1~} < i{~2~} < ... < i{~k~} ≤ N$ se numeşte _şmecher_ dacă pentru oricare doi indici consecutivi $i{~p~}$ şi $i{~p + 1~}$ (pentru orice $1 ≤ 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 ≤ i{~1~} < i{~2~} < ... < i{~k~} ≤ N$ se numeşte _şmecher_ dacă pentru oricare doi indici consecutivi $i{~p~}$ şi $i{~p + 1~}$ (pentru orice $1 ≤ 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$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $aquilla.out$ ...
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$.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
2 3 2
1 10 100
| 211
|
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") ==
