#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e7 + 10;
typedef long long ll;

ll k_d[MAXN];
bool is_prime[MAXN];
int prime[700000];
int cnt = 0;
ll n, d, q, l, r;
const ll MOD = 1e9 + 7;

inline ll mod(ll a) {
	return a >= MOD ? a - MOD : a;
}
inline ll qpow(ll a) {
	if (a == 0) return 0;
	unsigned exp = d;
	ll res = 1;
	for (; exp; exp >>= 1) {
		if (exp & 1) res = res * a % MOD;
		a = a * a % MOD;
	}
	return res;
}

inline ll F(ll x) {
	if (x <= 0) return 0;
	ll res = 0;
	for (register ll l = 1, r; l <= x; l = r + 1) {
		r = x / (x / l);
		res = (res + (k_d[r] - k_d[l - 1] + MOD) * (x / l)) % MOD;
	}
	return res;
}

int main() {
	scanf("%d%lld%d", &n, &d, &q);
	d %= (MOD - 1);
	is_prime[1] = true;
	k_d[1] = 1;
	for (register int i = 2; i <= n; ++i) {
		if (!is_prime[i]) {
			prime[cnt++] = i;
			k_d[i] = qpow(i);
		}
		for (register int j = 0; j < cnt; ++j) {
			if (prime[j] * i > n) break;
			is_prime[prime[j] * i] = false;
			k_d[prime[j] * i] = k_d[i] * k_d[prime[j]] % MOD;
			if (i % prime[j] == 0) break;
		}
	}
	for (register int i = 1; i <= n; ++i)
		k_d[i] = mod(k_d[i] + k_d[i - 1]);
	while (~scanf("%d%d", &l, &r))
		printf("%lld\n", mod(F(r) - F(l - 1) + MOD));
	return 0;
}