RT，用的是主席树，复杂度是$\,\mathcal{O}(n\log a_{i}\log n)\,$的，但是发现当$\,n=m=2\times 10^5\,$时跑出来$\,4400\,\text{ms}\,$

#include <bits/stdc++.h>
#define R register

namespace io
{
	template<typename types>
	inline void read(types &x)
	{
		x = 0; char ch = getchar();
		while (!isdigit(ch)) ch = getchar();
		while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
		return;
	}
	template<typename types>
	inline void write(const types &x)
	{
		if (x > 9) write(x / 10);
		putchar(x % 10 + '0'); return;
	}
	template<typename types>
	inline void writeln(const types &x) {write(x), putchar('\n'); return;}
}
using namespace io;
namespace problems
{
	const int N = 200010, M = 1000010, K = (N << 6) + (N << 5);
	const int mod = 1e9 + 7;
	int n, m;
	int primes[M], pcnt = 0;
	bool notprime[M];

	inline void getPrime(const int &up)
	{
		memset(notprime, false, sizeof(notprime));
		notprime[1] = true;
		for (R int i = 2; i <= up; ++ i)
		{
			if (!notprime[i]) primes[++ pcnt] = i;
			for (R int j = 1; j <= pcnt && 1ll * i * primes[j] <= up; ++ j)
			{
				notprime[i * primes[j]] = true;
				if (i % primes[j] == 0) break;
			}
		}
		return;
	}
	inline int ksm(int a, int b, const int &p)
	{
		int res = 1;
		while (b)
		{
			if (b & 1) res = 1ll * res * a % p;
			a = 1ll * a * a % p, b >>= 1;
		}
		return res;
	}

	struct CT
	// Chairman Tree
	{
		int l[K], r[K], prod[K];
		int last[N];
		int root[N], tot = 0;

		void init(void)
		{
			memset(l, 0, sizeof(l));
			memset(r, 0, sizeof(r));
			memset(last, 0 ,sizeof(last));
			memset(root, 0, sizeof(root));
			tot = 0; return;
		}
		inline int copynode(const int &p)
		{
			int id = ++ tot;
			l[id] = l[p], r[id] = r[p], prod[id] = (prod[p] ? prod[p] : 1);
			return id;
		}
		inline int insert(int p, const int &hist, const int &x, const int &k, const int &inl, const int &inr)
		{
			p = copynode(hist);
			prod[p] = 1ll * prod[p] * k % mod;
			if (inl == inr)
				return p;
			int mid = (inl + inr) >> 1;
			if (x <= mid) l[p] = insert(l[p], l[hist], x, k, inl, mid);
			else r[p] = insert(r[p], r[hist], x, k, mid + 1, inr);
			return p;
		}
		inline int ask(const int &p, const int &x, const int &y, const int &inl, const int &inr)
		{
			if (!p) return 1;
			if (x <= inl && inr <= y)
				return prod[p];
			int mid = (inl + inr) >> 1;
			if (x <= mid && y > mid)
				return 1ll * ask(l[p], x, y, inl, mid) * ask(r[p], x, y, mid + 1, inr) % mod;
			else
			{
				if (x <= mid) return ask(l[p], x, y, inl, mid);
				else return ask(r[p], x, y, mid + 1, inr);
			}
		}
	}ct;

	int main(void)
	{
		getPrime(M - 1);
		ct.init();

		read(n);
		int inpx;
		for (R int i = 1; i <= n; ++ i)
		{
			read(inpx);
			
			bool flag = true;
			int toins = 1;
			for (R int j = 1; j <= pcnt && primes[j] <= inpx; ++ j)
				if (inpx % primes[j] == 0)
				{
					int times = 0;
					while (inpx % primes[j] == 0)
					{
						if (++ times > 1) toins = 1ll * toins * primes[j] % mod;
						inpx /= primes[j];
					}
					if (times)
					{
						toins = 1ll * toins * (primes[j] - 1) % mod;
						if (ct.last[j])
						{
							int temp = 1ll * primes[j] * ksm(primes[j] - 1, mod - 2, mod) % mod;
							ct.root[i] = ct.insert(ct.root[i], ct.root[i - flag], ct.last[j], temp, 1, n);
							flag = false;
						}
						ct.last[j] = i;
					}
				}
			if (toins == 1) ct.root[i] = ct.root[i - 1];
			else
				ct.root[i] = ct.insert(ct.root[i], ct.root[i - flag], i, toins, 1, n);
		}
		read(m);
		int inpl, inpr;
		for (R int i = 1; i <= m; ++ i)
		{
			read(inpl), read(inpr);
			writeln(ct.ask(ct.root[inpr], inpl, inpr, 1, n));
		}

		return 0;
	}
}

int main()
{
	problems::main();

	return 0;
}