牛牛的最大公约数
题号：NC21546
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述


牛牛有一个区间[L,R]

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

那么我们知道一共有 种选法

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

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

输入描述:

输入一行包含4个整数N,K,L,R (1 ≤ N, K, L ≤ 109, L ≤ R ≤ 109)

0 ≤ R - L ≤ 105

输出描述:

对于每组数据输出一个整数
示例1

输入

复制 
2 2 2 4

输出

复制 
3
示例2

输入

复制 
2 100 2 4

输出

复制 
0
示例3

输入

复制 
1 5 5 5

输出

复制 
1
示例4

输入

复制 
73824 17347 9293482 9313482

输出

复制 
0
示例5

输入

复制 
222 222 222 22222

输出

复制 
339886855

备注:

子任务1：n <= 1000
子任务2：n <= 1000000
子任务3：n <= 1000000000