悲惨的记录

$\mathcal{Code}$：

#include <iostream>
#include <cstdio>
#define min(a, b) a < b ? a : b

using namespace std;

int n, m, n1, m1, T, pri[1000001], p1, p2, cnt, phi[1000001];
double ds[1000001];
bool vis[1000001];
long long sum[1000001];

int num(int n, int m) {
	if (n > m) {
		n ^= m, m ^= n, n ^= m;
	}
	long long ans = 0;
	for (int l = 1, r; l <= n; l = r + 1) {
		r = min(n * ds[(int)(n * ds[l])], m * ds[(int)(m * ds[l])]);
//		cout << "l = " << l << ' ' << "r = " << r << '\n';
//		cout << n << ' ' << m << ' ' << min(n / (n / l), m / (m / l)) << endl;
		ans = (ans + (long long)(phi[r] - phi[l - 1]) * (long long)(n * ds[l]) % 1000000007 * (long long)(m * ds[l]) % 1000000007) % 1000000007;
	}
	return ans;
}

void solve() {
	scanf("%d %d %d %d", &n, &m, &n1, &m1);
//	cout << num(n1, m1) << ' ' << num(n - 1, m1) << ' ' << num(n1, m - 1) << ' ' << num(n - 1, m - 1) << endl;
	printf("%d\n", ((num(n1, m1) - num(n - 1, m1) - num(n1, m - 1) + num(n - 1, m - 1)) % 1000000007 + 1000000007) % 1000000007);
}

void init() {
	phi[1] = 1;
	vis[1] = 1;
	for (int i = 2; i <= max(p1, p2); ++i) {
		if (!vis[i]) {
			pri[++cnt] = i;
			phi[i] = i - 1;
		}
		for (int j = 1; j <= cnt && i * pri[j] <= max(p1, p2); ++j) {
			vis[i * pri[j]] = 1;
			if (i % pri[j] == 0) {
				phi[i * pri[j]] = phi[i] * pri[j];
				break;
			} else {
				phi[i * pri[j]] = phi[i] * (pri[j] - 1);
			}
		}
	}
	for (int i = 1; i <= max(p1, p2); ++i) {
		phi[i] += phi[i - 1];
		ds[i] = (1.0 / i) * 1.000000001;
//		sum[i] = sum[i - 1] + phi[i];
	}
//	cout << sum[100] << endl;
}

int main() {
//	freopen("data.out", "r", stdin);
	scanf("%d %d %d", &T, &p1, &p2);
	init();
	while (T--) {
		solve();
	}
	return 0;  
}