În vacanţa de vară, Phineas şi Ferb vor să construiască un roller-coaster. În oraşul Danville de află N turnuri în linie dreaptă. Cel de-al i-lea turn de la stânga la dreapta are înălţimea h[i].

Un roller-coaster este format dintr-o submulţime R = {i_1, i_2, ... i_k} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i_1,i_2), (i_2,i_3), ..., (i_k-1, i_k)

Un roller-coaster este format dintr-o submulţime R = {i{~1~}, i{~2~}, ..., i{~k~}} din cele N turnuri şi pistele de roller-coaster care vor fi construite între perechile de turnuri (i{~1~}, i{~2~}), (i{~2~}, i{~3~}), ..., (i{~k-1~}, i{~k~})

Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea h_1 de un turn cu înălţimea h_2 are coeficientul de distracţie cmmdc(h_1,h_2). Coeficientul de distracţie al unui roller-coaster este egal cu suma coeficienţilor pistelor care îl alcătuiesc.

Este bine cunoscut faptul că o pistă care uneşte un turn cu înălţimea h{~1~} de un turn cu înălţimea h{~2~} are coeficientul de distracţie cmmdc(h{~1~}, h{~2~}). Coeficientul de distracţie al unui roller-coaster este egal cu suma coeficienţilor pistelor care îl alcătuiesc.

Marcel a promis că îi ajută pe Phineas şi Ferb să îşi pună planul în aplicare cu speranţa de a apărea şi el într-un episod.

h2. Date de intrare

In $rollercoaster.in$ se afla N, numarul de turnuri, iar pe linia a doua se afla cele N numere naturale nenule.

În fişierul de intrare rollercoaster.in se află N, numărul de turnuri, iar pe linia a doua se află cele N numere naturale nenule.

h2. Date de ieşire

În $rollercoaster.out$ se vor afla 2 numere, reprezentand suma maxima pe care o poate obtine Marcel insumand cei mai mari divizori comuni numerelor aflate pe pozitii consecutive in subsirul ales, cat si restul impartirii numarului de subsiruri optime la 10^9+7.

În fişierul de ieşire rollercoaster.out se vor afla 2 numere, reprezentând coeficientul maxim de distracţie ce poate fi obţinut de Marcel, precum şi numărul de roller-coastere prin care se obţine.

h2. Restricţii si precizari

h2. Restricţii si precizări

* Un subsir al sirului de numere de pe f oaie este un sir pe care il putem obtine inlaturand cateva numere din sirul mare.
* N<=250.000
* numerele din sir <=250.000
* pentru 20% din punctaj, N<=15
* pentru 40% din punctaj, N<=1000

* N ≤ 250 000
* h[i] ≤ 250 000, 1 ≤ i ≤ N
* pentru 20% din punctaj, N ≤ 15
* pentru 40% din punctaj, N ≤ 1000

h2. Exemplu