P7486 样例都过不了

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 1e6 + 9,MOD = 32465177,phi_MOD = MOD - 1;
int quick_pow(int x,int y){
	int ret = 1;
	while(y){
		if(y & 1)
			ret = ret * x % MOD;
		x = x * x % MOD;
		y >>= 1;
	}
	return ret;
}
int qpow(int x,int y){
	if(y >= 0)
		return quick_pow(x,y);
	return quick_pow(quick_pow(x,-y),MOD - 2);
}
int n;
bool is_not_prime[N] = {1,1};
int prime[N],top;
int mu[N]; 
void sieve(){
	mu[1] = 1;
	for(int i = 2;i <= n;i++){
		if(!is_not_prime[i]){
			prime[++top] = i;
			mu[i] = -1;
		}
		for(int j = 1;j <= top && i * prime[j] <= n;j++){
			is_not_prime[i * prime[j]] = 1;
			if(i % prime[j] == 0)
				break;
			mu[i * prime[j]] = -mu[i];
		}
	}
}
int f[N],g[N];
int x[N];int power[N],y[N];
int p[N],q[N];
void init(){
	f[0] = 1;g[0] = 0;
	for(int i = 1;i <= n;i++){
		f[i] = f[i - 1] * qpow(i,i) % MOD;
		g[i] = (g[i - 1] + i) % phi_MOD;
	}

	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j += i)
			(x[j] += i * mu[i]) %= phi_MOD;

	for(int i = 1;i <= n;i++)
		y[i] = 1;
	for(int i = 1;i <= n;i++)
		power[i] = qpow(i,i * mu[i]);
	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j += i)
			(y[j] *= power[i]) %= MOD;

	for(int i = 1;i <= n;i++){
		p[i] = (i * x[i]) % phi_MOD;
		q[i] = qpow(y[i] * qpow(i,x[i]),i);
	}
}
int h(int n,int m){
	return qpow(f[n],g[m]) * qpow(f[m],g[n]) % MOD;
}
int w(int n,int m){
	return g[n] * g[m] % phi_MOD;
}
int S(int n,int m){
	if(n > m)
		swap(n,m);
	int ret = 1;
	for(int T = 1;T <= n;T++){
		//cout << p[T] << ' ' << g[n / T] * g[m / T] << '\n';
		//cout << h(n / T,m / T) << ' ' << q[T] << '\n';
		(ret *= qpow(h(n / T,m / T),p[T]) * qpow(q[T],w(n / T,m / T)) % MOD) %= MOD;
	}
	return ret;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin >> T >> n;
	sieve();
	init();
	while(T--){
		int l,r;
		cin >> l >> r;
		int ans = S(r,r) * S(l - 1,l - 1) % MOD * qpow(S(l - 1,r),-2) % MOD;
		//cout << S(r,r) << '\n';
		cout << (ans + MOD) % MOD << '\n';
	}
	return 0;
}