rt

#include<bits/stdc++.h>
using namespace std;
const long long mod = 19260817;
namespace qwq{
	inline long long read(){
		long long n = 0;  
		long long f = 1;
		char c = getchar();
		while(c < '0' || c > '9'){
			if(c == '-') f = -1;
			c = getchar();
		}
		while(c >= '0' && c <= '9'){
			n = (n << 3) + (n << 1) + (c ^ 48);
			c = getchar();
		}
		return n * f;
	}
	inline void Write(long long x){
		if(x < 0){
			putchar('-');
			x = -x;
		}
		if(x > 9) Write(x / 10);
		putchar((x % 10) ^ 48);
		return;
	}
	inline void write(long long x, char c){
		Write(x);
		putchar(c);
	}
}
using namespace qwq;
static std::mt19937 sjzz;
long long suk[21] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
vector<long long> v;
long long a[1000010], belong[1000010], inv[1000010];
long long n, m, size, bnum, now = 1, ans[1000010], s[210][100010], b[1000010], id, g[1000010];
bool st[1010];
long long primes[1010], cnt;
unordered_map<int, int> mp;
struct node{
    long long l, r, id;
    bool operator < (const node &A){
        return (belong[l] ^ belong[A.l]) ? belong[l] < belong[A.l] : (belong[l] & 1) ? r < A.r : r > A.r;
    }
} q[1000010];
void get_primes(long long n1){
	for(long long i = 2; i <= n1; i++){
		if(!st[i]) primes[++cnt] = i;
		for(long long j = 1; primes[j] <= n1 / i; j++){
			st[i * primes[j]] = true;
			if(i % primes[j] == 0) break;
		}
	}
}
void getinv(long long x){
	inv[1] = 1;
	for(long long i = 2; i <= x; i++){
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
}
long long qpow(long long a1, long long b1, long long mod1){
    long long base = a1, ans1 = 1ll;
    if(a1 == 1) return 1;
	while(b1 > 0){
		if(b1 & 1){
			ans1 *= base;
			ans1 %= mod1;
		}
		base *= base;
		base %= mod1;
		b1 >>= 1;
	}
    return ans1;
}
bool check(long long n1, long long a1, long long b1, long long x){
    long long v1 = qpow(x, a1, n1);
    if(v1 == 1) return true;
    long long j = 1;
    while(j <= b1){
        if(v1 == n-1) break;
        v1 *= v1;
        v1 %= n1;
        j++;
    }
    if(j > b1) return false;
    return true;
}
bool Miller_Rabin(long long x){
    if(x < 3 || x % 2 == 0) return x == 2;
    if(x % 3 == 0) return x == 3;
    if(x % 4 == 0) return false;
    if(x % 6 != 1 && x % 6 != 5) return false;
    if(x > 37){
        long long a1 = x-1, b1 = 0;
        while(a1 % 2 == 0){
            a1 /= 2;
            b1++;
        }
        for(long long i = 1; i <= 12; i++){
            if(!check(x, a1, b1, suk[i])) return false;
        }
        return true;
    }else{
        for(long long i = 2; i <= 12; i++){
            if(x == suk[i]) return true;
        }
        return false;
    }
}
long long gcd(long long a1, long long b1){
    if(!b1) return a1;
    return gcd(b1, a1 % b1);
}
long long f(long long x, long long c, long long mod1){
    return (x * x % mod1 + c) % mod1;
}
long long ABS(long long x){
	if(x < 0) return -x;
	return x;
}
long long Pollard_Rho(long long n1){
    if(n1 == 4) return 2;
    std::uniform_int_distribution<long long> Rand(3 , n1 - 1);
    long long x = Rand(sjzz), c = Rand(sjzz), y = f(f(x, c, n1), c, n1);
    x = f(x, c, n1);
    for(long long lim = 1; x != y; lim = min(lim << 1, 64ll)){
        long long cnt1 = 1;
        for(long long i = 0; i < lim; i++){
            cnt1 *= ABS(x-y);
            cnt1 %= n1;
            if(!cnt1) break;
            x = f(x, c, n1), y = f(f(y, c, n1), c, n1);
        }
        long long d = gcd(cnt1, n1);
        if(d != 1) return d;
    }
    return n1;
}
void add(long long x){
    if(a[x]){
        now = now * inv[g[a[x]]] % mod * (g[a[x]] + 1) % mod;
        g[a[x]]++;
        if(b[x]){
            now = now * inv[g[b[x]]] % mod *(g[b[x]] + 1) % mod;
            g[b[x]]++;
        }
    }
}
void del(long long x){
    if(a[x]){
        now = now * inv[g[a[x]]] % mod *(g[a[x]] - 1) % mod;
        g[a[x]]--;
        if(b[x]){
            now = now * inv[g[b[x]]] % mod *(g[b[x]] - 1) % mod;
            g[b[x]]--;
        }
    }
}
int main(){
	n = read(), m = read();
	get_primes(1000);
	getinv(n << 2);
    size = sqrt(n);
    bnum = (n + size - 1) / size;
    for(long long i = 1; i <= bnum; i++){
        for(long long j = (i - 1) * size + 1; j <= i * size; j++){
            belong[j] = i;
        }
    }
    for(long long i = 1; i <= n; i++){
    	a[i] = read();
    	for(long long j = 1; j <= cnt; j++){
    		while(!(a[i] % primes[j])) a[i] /= primes[j], ++s[j][i];
    		s[j][i] += s[j][i-1];
		}
        if(a[i] > 1 && Miller_Rabin(a[i])){
            b[i] = a[i];
            while(b[i] == a[i]) b[i] = Pollard_Rho(a[i]);
            a[i] /= b[i];
        }
        if(a[i] > 1){
            if(b[i]){
                if(!mp.count(b[i])) mp[b[i]] = ++id;
                b[i] = mp[b[i]];
            }
            if(!mp.count(a[i])) mp[a[i]] = ++id;
            a[i] = mp[a[i]];
        }else a[i] = 0;
	}
    for(long long i = 1; i <= id; i++){
        g[i] = 1;
    }
    for(long long i = 1; i <= m; i++){
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    }
    sort(q+1, q+m+1);
    long long l = 1, r = 0;
    for(long long i = 1; i <= m; i++){
        long long ql = q[i].l, qr = q[i].r;
        while(l > ql) add(--l);
        while(r < qr) add(++r);
        while(l < ql) del(l++);
        while(r > qr) del(r--);
        long long k = now;
        for(long long j = 1; j <= cnt; j++){
            k *= (s[j][r] - s[j][l-1] + 1);
            k %= mod;
        }
        ans[q[i].id] = k;
    }
    for(long long i = 1; i <= m; i++){
        write(ans[i], '\n');
    }
    return 0;
}