问题4424--粗题⼈不考你没学过的算法

4424: 粗题⼈不考你没学过的算法

[命题人 : ]
时间限制 : 10.000 sec  内存限制 : 128 MB

题目描述

粗题⼈症重承诺此题不考你没学过的算法

给你⼀个区间[L,R]

需要选择N个数,这N个数都在这个区间范围内

那么我们知道⼀共有[R-L+1]^N种选法

假如我们想要这N个数的最⼤公约数恰好是K

请问⼀共有多少种选法,输出答案对1e9+7取模

输入

 多组测试数据 对于每组数据,输⼊⼀⾏包含4个整数N,K,L,R(1<=N,K,L<=10^9,L<=R<=10^9)

(0<=R-L<=10^5)

输出

 对于每组数据输出⼀个整数

样例输入 Copy

2 2 2 4
2 100 2 4
1 5 5 5
73824 17347 9293482 9313482
222 222 222 22222

样例输出 Copy

3
0
1
0
339886855

来源/分类