gcdseq

Gcdseq

== include(page="template/taskheader" task_id="gcdseq") ==

Gojo are in faţa lui un şir de $N$ păpuşi cu diverse înălţimi *distincte*. Gojo vinde căte o subsecvenţă continuă de păpuşi odată. O subsecvenţă continuă de lungime $L$ cu înălţimea maximă egală cu $M$ se vinde cu preţul de $G$ lei, unde $G$ este cel mai mare divizor comun al lui $L$ şi $M$. Gojo a primit dintr-o dată o grămadă de comenzi, câte una pentru fiecare subsecvenţă continuă posibilă. El se întreabă acum: care e suma preţurilor comenzilor ce le-am primit?

Teognis are in faţa lui un şir de $N$ poezii lirice cu diverse frumuseţi *distincte*. Teognis vinde căte o subsecvenţă continuă de poezii deodată. O subsecvenţă continuă de lungime $L$ cu frumuseţea maximă egală cu $M$ se vinde cu preţul de $G$ lei, unde $G$ este cel mai mare divizor comun al lui $L$ şi $M$. Teognis a primit dintr-o dată o grămadă de comenzi, câte una pentru fiecare subsecvenţă continuă posibilă. El se întreabă acum: care e suma preţurilor comenzilor ce le-am primit?

h2. Date de intrare

Fişierul de intrare $gcdseq.in$ conţine pe primul rând pe $N$, numărul de păpuşi, şi pe al doilea rând înălţimile păpuşilor.

Fişierul de intrare $gcdseq.in$ conţine pe primul rând pe $N$, numărul de poezii, şi pe al doilea rând frumuseţile poeziilor.

h2. Date de ieşire

În fişierul de ieşire $gcdseq.out$ se va afişa suma cerută, modulo $10^9^+7$.

În fişierul de ieşire $gcdseq.out$ se va afişa suma cerută.

h2. Restricţii
* $1 ≤ N ≤ 100 000$.

* $1 ≤ înălţimea unei păpuşi ≤ 400 000$.

* $1 ≤ frumuseţea unei poezii ≤ 400 000$.

* Pentru 10 puncte, $N ≤ 100$.
* Pentru alte 20 de puncte, $N ≤ 1 000$.