Ученье --- свет, а неученье --- тьма

Последнее время Альф вообще ничего не делает. Даже ничего не сломал за последнюю неделю. Линн решила, что ему пора прекратить бездельничать и начать учиться.

Начать обучение она решила с несложной задачи: дан массив натуральных чисел. С массивом производятся две операции:

• 0 i x --- присвоить $i$-му элементу массива значение $x$;
• 1 l r --- вывести количество делителей у произведения чисел на отрезке с $l$ по $r$. Это число может быть довольно большим, поэтому ответ требуется вывести по модулю $10^9+7$.

Альф тайно влюблен в Линн, поэтому не может ей отказать. Но и работать он не хочет. Поэтому он попросил вас в тайне от Линн написать программу, которая решает данную задачу.

В первой строке входного файла дано число $n$ ($1 \le n \le 5 \cdot 10^4$) --- количество элементов массива.

Во второй строке дано $n$ чисел $a_i$ ($1 \le a_i \le 10^4$) --- элементы массива.

В третьей строке дано число $q$ ($1 \le q \le 10^4$) --- количество запросов.

В каждой из следующих $q$ строк записано по три числа. Если первое из этих чисел равно 0, то это запрос обновления элемента массива, если же первое число равно 1, то это запрос на нахождение количества делителей у произведения чисел на отрезке по модулю $10^9+7$.

Гарантируется, что во всех запросах $1 \le i, l, r \le n; 1 \le x \le 10^4$.

На каждый запрос нахождения количества делителей выведите в отдельной строке выходного файла ответ --- количество делителей у произведения всех чисел на данном отрезке по модулю $10^9+7$.