记录编号	158267	评测结果	AAAAAAAAAA
题目名称	[CQOI 2015] 选数	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-04-13 20:36:56	内存使用	0.29 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#ifdef DEBUG
#include <sys/timeb.h>
#endif
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define getc() getchar() 
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
#ifdef DEBUG
#include <sys/timeb.h>
timeb Tp;
#endif
/***********************************************************************/
const int maxn = 100004, mod = 1000000007;
typedef long long LL;
inline int powmod(int a, int n){
	int ans = 1;
	while(n){if(n & 1)ans = (LL)ans * a % mod;a = (LL)a * a % mod;n >>= 1;}
	return ans;
}

inline void work(){
	int f[maxn], N, K, L, H, i, j, t, *it;getd(N), getd(K), getd(L), getd(H);
	L = (L - 1) / K;H /= K;
	int len = H - L;
	for(i = len, it = f + i;i;--i, --it){
		t = H / i - L / i;//多少个i的倍数
		*it = (powmod(t, N) + mod - t) % mod;
		for(j = i << 1;j <= len;j += i)
			*it = (*it + mod - f[j]) % mod;
	}
	if(L <= 1 && H > 1)++f[1];
	printf("%d\n", f[1]);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	ftime(&Tp);
	time_t Begin_sec = Tp.time, Begin_mill = Tp.millitm;
#elif !defined ONLINE_JUDGE
	SetFile(cqoi15_number);
#endif
	work();

#ifdef DEBUG
	ftime(&Tp);
	printf("\n%.3lf sec \n", (Tp.time - Begin_sec) + (Tp.millitm - Begin_mill) / 1000.0);
#endif
	return 0;
}