We know that there are $(H-L+1)^N$ ways to choose $N$ integers from the interval $[L, H]$ (where $L$ and $H$ are integers). Little Z is curious about the properties of the greatest common divisor (GCD) of the numbers chosen in this way. He decides to calculate the GCD of the $N$ integers for every possible selection to study it further. However, he soon discovers that the workload is 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 a greatest common divisor exactly equal to $K$. Since the number of schemes can be large, you only need to output the result modulo $1000000007$.

Input

The input contains one line with four space-separated positive integers: $N$, $K$, $L$, and $H$.

Output

Output a single integer representing the number of schemes.

Examples

Input 1

2 2 2 4

Output 1

3

Note

All possible selection schemes are: $(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)$. Among these, only 3 groups have a greatest common divisor equal to 2: $(2, 2), (2, 4), (4, 2)$.

Constraints

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