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

class RandomGCD {
	public:
		long long Pow(long long a, long long e, long long mod) {
			if(e <= 0) return 1;
			long long x =Pow(a,e/2,mod);
			x =(x*x)%mod;
			if(e%2 != 0) x =(x*a)%mod;
			return x;} 
	
		long long mod =1000000007;
		int High,Low,M;
	
		long long count(vector<long long> &A, int D) {
			if(High/D == Low/D) return 0;
			if(A[D] >= 0) return A[D];
			A[D] =Pow(High/D-Low/D,M,mod)-(High/D-Low/D);
			for(int i =2; i <= (High-Low)/D; i++)
				if(High/(D*i)-Low/(D*i) > 1) A[D] =(A[D]+mod-count(A,D*i))%mod;
			return A[D];}
	
		int countTuples(int N, int K, int low, int high) {
			Low =(low-1)/K;
			High =high/K;
			M =N;
			vector<long long> A(High-Low+1,-1);
			return count(A,1)+((Low < 1 && High >= 1)?1:0);}
};