Description

We know that selecting $N$ integers from the interval $[L, H]$ (where $L$ and $H$ are integers) yields $(H - L + 1)^N$ schemes. Little z is curious about the pattern of the greatest common divisor of the numbers selected in this way. He decides to compute the greatest common divisor of the $N$ integers for every scheme for further study. However, he soon finds the workload too large, so he asks for your help. Your task is simple: Little z will give you an integer $K$, and you need to answer how many selection schemes have their greatest common divisor exactly equal to $K$.

Since the number of schemes can be large, you only need to output the remainder modulo $10^9+7$.

Input Format

The input consists of one line containing four space-separated positive integers, in order: $N, K, L, H$.

Output Format

Output a single integer, which is the remainder of the required count modulo $10^9+7$.

2 2 2 4

3

Hint

Sample 1 Explanation.

All possible selection schemes: $(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)$.

Among them, those with greatest common divisor equal to $2$ are only $3$ groups: $(2, 2), (2, 4), (4, 2)$.

Constraints.

For $100\%$ of the testdata, $1\le N, K\le 10^9$, $1\le L\le H\le 10^9$, $H - L\le 10^5$.

Translated by ChatGPT 5