Бяцхан заан хоосон биш эерэг бүхэл тоонуудын олонлогийн ХБЕХ-г (хамгийн бага ерөнхий хуваагдагч) олох дуртай. $k$ ширхэг $x_{1}, x_{2}, ..., x_{k}$ эерэг бүхэл тоонуудын ХБЕХ нь $x_{i}$ тоонуудад бүгдэд нь хуваагддаг хамгийн бага эерэг бүхэл тоо юм.

$b_{1}, b_{2}, ..., b_{n}$ бүхэл тоонуудын дараалал байна гэж бодъё. Энэ дарааллын ХБЕХ-г $lcm(b_{1}, b_{2}, ..., b_{n})$ гэж, тэдгээрийн хамгийн ихийг нь $max(b_{1}, b_{2}, ..., b_{n})$ гэж тэмдэглэе. Хэрвээ $lcm(b_{1}, b_{2}, ..., b_{n}) = max(b_{1}, b_{2}, ..., b_{n})$ бол Бяцхан заан $b$ дарааллыг сайн дараалал гэж үзнэ.

Бяцхан заанд $a_{1}, a_{2}, ..., a_{n}$ бүхэл тоонуудын дараалал байна.$1 ≤ b_{i} ≤ a_{i}$ нөхцлийг хангадаг бүх $i$ $(1 ≤ i ≤ n)$-н хувьд $b_{1}, b_{2}, ..., b_{n}$ бүхэл тоонуудын сайн дарааллын тоог ол. Хариулт нь хэтэрхий том тоо байж болох тул хариуг $1000000007$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Оролт

Эхний мөр нь $n$ $(1 ≤ n ≤ 10^{5})$ эерэг бүхэл тоог агуулна. Энэ нь $a$ дараалалд байх элементүүдийн тоо юм. Хоёр дахь мөр нь $a$ дарааллын $n$ ширхэг зайгаар тусгаарлагдсан $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 10^{5})$ бүхэл тоонуудыг агуулна.

Гаралт

Нэг мөрөнд нэг бүхэл тоо хэвлэнэ. Энэ нь бодлогын хариуг $1000000007$ тоонд хуваагаад гарсан үлдэгдэл юм.