Counting Selections with Specified GCD

You are given four integers L, H, N and K. Consider the interval \([L,H]\) where both L and H are integers. From this interval, one can choose N integers (with replacement) in \((H-L+1)^N\) different ways.

For each selection, let \(g = \gcd(a_1, a_2, \dots, a_N)\) be the greatest common divisor of the N chosen numbers. Your task is to count the number of selections for which \(g = K\). Since the answer can be very large, output it modulo \(10^9+7\).

Hint: Note that if \(g = K\) then every chosen number must be divisible by \(K\). Let \(x_i = \frac{a_i}{K}\); the problem then reduces to counting the number of sequences \(x_1, x_2, \dots, x_N\) (where each \(x_i\) is taken from the interval \([L', H']\) with \(L' = \lceil \frac{L}{K} \rceil\) and \(H' = \lfloor \frac{H}{K} \rfloor\)) such that \(\gcd(x_1, x_2, \dots, x_N) = 1\). This can be solved using the Möbius inversion formula: \[ \text{Answer} = \sum_{d \ge 1} \mu(d)\left(\text{count}_d\right)^N\quad \text{mod }10^9+7, \] where \(\text{count}_d = \left\lfloor \frac{H'}{d} \right\rfloor - \left\lceil \frac{L'}{d} \right\rceil + 1\) and \(\mu(d)\) is the Möbius function.

inputFormat

The input consists of a single line with four space-separated integers: L, H, N and K.

Constraints: It is guaranteed that L and H are integers with L ≤ H, and N and K are positive integers.

outputFormat

Output a single integer: the number of selections for which the greatest common divisor equals K, modulo \(10^9+7\).

sample

1 10 2 1

63