403359: GYM101138 G LCM-er

You are given four integers n, a, b and x. Your task is to count modulo 10⁹ + 7 the number of sequences of integers A satisfying the following conditions:

1. A should contain exactly n elements.
2. a ≤ A₁ ≤ A₂ ≤ ... ≤ A_n ≤ b (the sequence is non-decreasing and all integers are between a and b, inclusive).
3. The least common multiple of all numbers in A should be divisible by x.

The only line of the input contains four integers n, a, b and x (1 ≤ n ≤ 100, 1 ≤ a, b, x ≤ 10⁹, a ≤ b).

Count sequences of integers satisfying the given conditions. Print the answer modulo 10⁹ + 7.

2 1 7 6

9

1 1 50 7

7

In the first sample there are 9 valid sequences: (1, 6), (2, 3), (2, 6), (3, 4), (3, 6), (4, 6), (5, 6), (6, 6), (6, 7).