#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define ui unsigned int
#define i128 __int128
#define mem(x, y) memset(x, y, sizeof x)
#define lid (id << 1)
#define rid (id << 1 | 1)
#define popct(x) __builtin_popcount(x)
#define popctll(x) __builtin_popcountll(x)
const int N = 1e5+5;
const int intmin = -0x3f3f3f3f, intmax = 0x3f3f3f3f;
const ll llmin = -0x3f3f3f3f3f3f3f3f, llmax = 0x3f3f3f3f3f3f3f3f;
#ifdef ONLINE_JUDGE
#define __OY_FASTIO__
#define cin IO::InputHelper::get_instance()
#define cout IO::OutputHelper::get_instance()
#ifndef INPUT_FILE
#ifdef OY_LOCAL
#define INPUT_FILE "in.txt"
#else
#define INPUT_FILE ""
#endif
#endif
#ifndef OUTPUT_FILE
#ifdef OY_LOCAL
#define OUTPUT_FILE "out.txt"
#else
#define OUTPUT_FILE ""
#endif
#endif
//https://github.com/old-yan/CP-template/blob/main/IO/FastIO.md
namespace IO {
	using size_type = size_t;
	static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
	struct InputHelper {
		FILE *m_file_ptr;char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;bool m_ok;
		InputHelper &set_bad() { return m_ok = false, *this; }
		template <size_type BlockSize>
		void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;memmove(m_buf, m_cursor, a), m_cursor = m_buf;size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;}
		template <typename Tp, typename BinaryOperation>
		InputHelper &fill_integer(Tp &ret, BinaryOperation op) {if (!isdigit(*m_cursor)) return set_bad();ret = op(Tp(0), *m_cursor - '0');size_type len = 1;while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');m_cursor += len;return *this;}
		explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
		~InputHelper() { fclose(m_file_ptr); }
		static InputHelper &get_instance() {static InputHelper s_obj(input_file);return s_obj;}
		static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }static bool is_endline(char c) { return c == '\n' || c == EOF; }
		const char &getchar_checked() {_reserve<1>();return *m_cursor;}const char &getchar_unchecked() const { return *m_cursor; }
		void next() { ++m_cursor; }
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());next();return fill_integer(num, std::minus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {while (is_blank(getchar_checked())) next();_reserve<MAX_INTEGER_SIZE>();return fill_integer(num, std::plus<Tp>());}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		InputHelper &operator>>(Tp &num) {
			bool neg = false, integer = false, decimal = false;while (is_blank(getchar_checked())) next();_reserve<MAX_FLOAT_SIZE>();
			if (getchar_unchecked() == '-') {neg = true;next();}if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
			if (isdigit(getchar_unchecked())) {integer = true;num = getchar_unchecked() - '0';while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');}
			if (getchar_unchecked() == '.') if (next(), isdigit(getchar_unchecked())) {if (!integer) num = 0;decimal = true;Tp unit = 0.1;num += unit * (getchar_unchecked() - '0');while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');}
			if (!integer && !decimal) return set_bad();if (neg) num = -num;return *this;
		}
		InputHelper &operator>>(char &c) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();c = getchar_checked(), next();return *this;}
		InputHelper &operator>>(std::string &s) {while (is_blank(getchar_checked())) next();if (getchar_checked() == EOF) return set_bad();s.clear();do {s += getchar_checked();next();} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);return *this;}
		explicit operator bool() { return m_ok; }
	};
	struct OutputHelper {
		FILE *m_file_ptr = nullptr;char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;uint64_t m_float_reserve, m_float_ratio;
		void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
		template <size_type BlockSize> void _reserve() {size_type a = m_end - m_cursor;if (a >= BlockSize) return;_write();}
		OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
		static OutputHelper &get_instance() {static OutputHelper s_obj(output_file);return s_obj;}
		~OutputHelper() { flush(), fclose(m_file_ptr); }
		void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(std::pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
		OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
		void putchar(const char &c) {if (m_cursor == m_end) _write();*m_cursor++ = c;}
		template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;if (ret >= 0) do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);else {putchar('-');do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;while (ret);}for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {_reserve<MAX_INTEGER_SIZE>();size_type len = 0;do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;while (ret);for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));m_cursor += len;return *this;}
		template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
		OutputHelper &operator<<(Tp ret) {
			if (ret < 0) {putchar('-');return *this << -ret;}ret *= m_float_ratio;uint64_t integer = ret;if (ret - integer >= 0.4999999999) integer++;do {*m_temp_buf_cursor++ = '0' + integer % 10;integer /= 10;} while (integer);
			if (m_temp_buf_cursor > m_temp_buf_dot) {do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf_dot);putchar('.');}else {putchar('0'), putchar('.');for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');}
			do putchar(*--m_temp_buf_cursor);while (m_temp_buf_cursor > m_temp_buf);
			return *this;
		}
		OutputHelper &operator<<(const char &ret) {putchar(ret);return *this;}
		OutputHelper &operator<<(const char *ret) {while (*ret) putchar(*ret++);return *this;}
		OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
	};
	InputHelper &getline(InputHelper &ih, std::string &line) {line.clear();if (ih.getchar_checked() == EOF) return ih.set_bad();while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();if (ih.getchar_unchecked() != EOF) ih.next();return ih;}
}using IO::getline;
#endif
namespace funcqwq{
	mt19937 rd(time(0));
	inline ll qpow(ll a, ll b){ll res = 1;for (;b;a *= a, b >>= 1)if (b & 1)res = res * a;return res;}
	inline ll qpow(ll a, ll b,  ll p){ll res = 1;for (;b;a = (i128)a * a % p,b >>= 1){(b & 1 ? res = (i128)res * a % p : 0);}return res;}
	inline ll _gcd(ll a, ll b){if (!a || !b) return a | b;int t = __builtin_ctzll(a | b);a >>= __builtin_ctzll(a);do{b >>= __builtin_ctzll(b);if (b < a) swap(a, b);b -= a;}while(b);return a << t;}
	inline ll llrd(){return (rd() << 10) ^ ((rd() ^ 0x28208a20a08a28ac));}
	inline int intrd(){return ((rd() >> 2) ^ 0x12345678);}
	bool miller_rabin(const ll p){
		if (p < 64) return 0x28208a20a08a28ac >> p & 1;if (!(p % 2)||!(p % 3)||!(p % 5)||!(p % 7)) return 0;
		ll d = p - 1;short k = __builtin_ctzll(d);d >>= k;
		for (register short asd = 0;8 - asd;++asd){
			ll pw = qpow(llrd()%(p-1)+1,d,p),pw1;
			for (register short j = 0;k - j;++j){pw1=(i128)pw*pw%p;if(pw1==1&&(pw^1)&&(pw^(p - 1)))return 0;pw = pw1;}
			if (pw ^ 1) return 0;
		}
		return 1;
	}
	namespace PRqwq{
		inline ll PR(ll x){
			if (x == 4) return 2;
			ll c= llrd() % (x - 2) + 1;ll s = llrd() % (x - 2) + 1, t = s;
			s = (i128)(s * s + c) % x;t = (i128)(t * t + c) % x;t = ((i128)t * t + c) % x;
			for (short i = 1;s ^ t;i = min(128, i << 1)){
				ll sum = 1, sum1;
				for (short j = 0;i - j;++j){
					if (!(sum1 = (i128)sum * abs(t - s) % x)) break;
					sum = sum1;s = ((i128)s * s + c) % x;t = ((i128)t * t + c) % x;t = ((i128)t * t + c) % x;
				}
				if ((sum1 = _gcd(sum, x)) ^ 1) return sum1;
			}
			return x;
		}
		ll mxfc;
		vector<pair<ll, int> > fc;
		inline void maxfac(ll x){if (x<2||x<=mxfc)return;if(miller_rabin(x))return(mxfc<x?mxfc=x:0),void();ll tmp=x;while(tmp>=x)tmp=PR(tmp);while(!(x%tmp))x/=tmp;maxfac(x),maxfac(tmp);}
		inline ll max_fac(ll x){mxfc = 1;maxfac(x);return mxfc;}
		inline void getfac(ll x){if(x==1)return;mxfc=1;maxfac(x);if(mxfc==x)return fc.emplace_back(mxfc,1),void();else{short c=0;while(!(x%mxfc))x/=mxfc,++c;fc.emplace_back(mxfc,c);getfac(x);}}
		inline vector<pair<ll, int> > get_fac(ll x, bool op = 0){fc.clear();getfac(x);if(op)reverse(fc.begin(),fc.end());return fc;}
	}
	using PRqwq::max_fac;
	using PRqwq::get_fac;
}
using funcqwq::qpow;
using funcqwq::miller_rabin;
using funcqwq::_gcd;
using funcqwq::max_fac;
using funcqwq::llrd;
using funcqwq::get_fac;
using funcqwq::intrd;
namespace tianyu{
	const ll mod = 19260817;
	int n, m;
	int a[N], b[N * 10];
	vector<pair<ll, int> > fac[N];
	ll cnt[N * 10], ans;
	ll inv[200005];
	int belong[N], blen;
	struct que{
		int l, r, id;
	}q[N];
	bool cmp(que a, que b){
		return belong[a.l] != belong[b.l] ? a.l < b.l : (belong[a.l] & 2 ? a.r < b.r : a.r > b.r);
	}
	void add(int p){
		for (auto j : fac[p]){
			ans = ans * inv[cnt[j.first]] % mod * (cnt[j.first] += j.second) % mod;
		}
	}
	void del(int p){
		for (auto j : fac[p]){
			ans = ans * inv[cnt[j.first]] % mod * (cnt[j.first] -= j.second) % mod;
		}
	}
	ll ans1[N];
	bool isprime[1005];
	int prime[1005], cccnt;
	int iid[1005];
	int ccccnt[N][170];
	void awa(){
		for (int i = 2;i <= 1e3;i++){
			if (!isprime[i]) prime[++cccnt] = i;
			for (int j = 1;j <= cccnt && i * prime[j] <= 1e3;j++){
				isprime[i * prime[j]] = 1;
				if (i % prime[j] == 0) break;
			}
		}
		for (int i = 1;i <= cccnt;i++) iid[prime[i]] = i;
		cin >> n >> m;
		int len = 0;
		blen = sqrt(n);
		for (int i = 1;i <= n;i++){
			cin >> a[i];
			belong[i] = (i - 1) / blen + 1;
			fac[i] = get_fac(a[i]);
			for (int j = 1;j <= cccnt;j++) ccccnt[i][j] = ccccnt[i - 1][j];
			for (int j = fac[i].size() - 1;j >= 0;j--){
				if (fac[i][j].first <= 1000){
					ccccnt[i][iid[fac[i][j].first]] += fac[i][j].second;
					fac[i].pop_back();
				}
				else{break;}
			}
			for (auto j : fac[i]){
				b[++len] = j.first;
			}
		}
		sort(b + 1, b + 1 + len);
		len = unique(b + 1, b + 1 + len) - b - 1;
		for (int i = 1;i <= len;i++) cnt[i] = 1;
		for (int i = 1;i <= n;i++){
			for (auto &j : fac[i]){
				j.first = lower_bound(b + 1, b + 1 + len, j.first) - b;
			}
		}
		for (int i = 1;i <= 2 * n + 1;i++) inv[i] = qpow(i, mod - 2, mod);
		inv[0] = 1;
		for (int i = 1;i <= m;i++){
			cin >> q[i].l >> q[i].r;
			q[i].id = i;
		}
		ans = 1;
		sort(q + 1, q + 1 + m, cmp);
		int l = 1, r = 0;
		for (int i = 1;i <= m;i++){
			while (r < q[i].r) add(++r);
			while (r > q[i].r) del(r--);
			while (l > q[i].l) add(--l);
			while (l < q[i].l) del(l++);
			ans1[q[i].id] = ans;
			for (int j = 1;j <= cccnt;j++){
				ans1[q[i].id] = ans1[q[i].id] * (ccccnt[r][j] - ccccnt[l - 1][j] + 1) % mod;
			}
		}
		for (int i = 1;i <= m;i++) cout << ans1[i] << '\n';
	}
}
signed main(){
	int T = 1;
	while (T--) tianyu::awa();
	return 0;
}