У Юры есть очень самый обыкновенный и скучный массив \(a\) длины \(n\). Казалось бы, ничего скучнее быть не может, но Владик так не думает!
Чтобы сделать массив Юры более скучным, Владик решил сделать \(q\) скучных запросов. Каждый запрос состоит из двух целых чисел \(x\) и \(y\). Далее для вычисления границ \(l\) и \(r\) данного запроса используется формула: \(l = (last + x) \bmod n + 1\), \(r = (last + y) \bmod n + 1\), где \(last\) — это ответ на предыдущий запрос (изначально он равен нулю), а \(\bmod\) — это операция взятия остатка от деления. Если получилось, что \(l > r\), то их значения нужно поменять местами.
Когда Владик наконец посчитал границы \(l\) и \(r\) для текущего запроса, то он захотел узнать значение наименьшего общего кратного (НОК) на отрезке \([l; r]\) для исходного массива \(a\) по модулю \(10^9 + 7\). НОК некоторого набора элементов — это наименьшее натуральное число, которое делится на каждое из чисел данного набора. Посчитанный НОК будет являться ответом на текущий запрос.
Помогите Владику и выведите ответ на каждый запрос!