배움은 빛, 배우지 않음은 어둠

최근 알프는 아무것도 하지 않고 있다. 지난 일주일 동안에는 무언가를 망가뜨린 일조차 없다. 린은 그가 빈둥거리는 것을 그만두고 공부를 시작할 때가 되었다고 판단했다.

린은 공부를 간단한 문제로 시작하기로 했다. 자연수로 이루어진 배열이 주어진다. 이 배열에 대해 다음 두 가지 연산을 수행한다.

• 0 i x: 배열의 $i$번째 원소에 값 $x$를 대입한다.
• 1 l r: 구간 $l$부터 $r$까지 원소의 곱에 대한 약수의 개수를 출력한다. 이 값은 매우 클 수 있으므로, 답은 $10^9+7$로 나눈 나머지로 출력한다.

알프는 린을 몰래 좋아하기 때문에 그녀의 부탁을 거절하지 못한다. 하지만 일을 하기는 싫다. 그래서 린 몰래 이 문제를 푸는 프로그램을 작성해 달라고 당신에게 부탁했다.

첫째 줄에 배열의 원소 개수 $n$ ($1 \le n \le 5 \cdot 10^4$)이 주어진다.

둘째 줄에 배열의 원소 $a_i$ ($1 \le a_i \le 10^4$) $n$개가 주어진다.

셋째 줄에 질의의 개수 $q$ ($1 \le q \le 10^4$)가 주어진다.

이후 $q$개의 줄에 정수 세 개가 각각 주어진다. 첫 번째 수가 0이면 배열 원소를 갱신하는 질의이고, 1이면 구간 곱의 약수 개수를 구하는 질의이다.

모든 질의에서 $1 \le i, l, r \le n$과 $1 \le x \le 10^4$이 보장된다.

번호가 1인 각 질의마다, 주어진 구간에 있는 모든 수의 곱의 약수 개수를 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.