G. LCM-er
time limit per test
0.5 секунд
memory limit per test
256 мегабайт
input
stdin
output
stdout

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

  1. A should contain exactly n elements.
  2. a ≤ A1 ≤ A2 ≤ ... ≤ An ≤ 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.
Input

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

Output

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

Examples
Input
2 1 7 6
Output
9
Input
1 1 50 7
Output
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).