Artem vs. Mansur

Artem had a sequence x of n numbers, where 1 ≤ n ≤ 100. This sequence satisfied the condition: 1 ≤ L ≤ x[1] ≤ x[2] ≤ ... ≤ x[n] ≤ R ≤ 10^9, and the least common multiple (LCM) of these numbers was divisible by a (1 ≤ a ≤ 10^9). However, Mansur came and stole the sequence x, leaving Artem unable to recall the exact numbers. He only remembers the values of n, L, R, and a. Artem wants to reconstruct the sequence by first determining how many such sequences could exist with the given n, L, R, and a. Your task is to write a program to find this number.

Input

The input consists of a single line with four positive integers, separated by spaces: n, L, R, a.

Output

Output a single integer, which is the number of possible sequences. Since this number can be very large, provide the result modulo 10^9 + 7.

Examples

Note

For example, in the first test case, the valid sequences are:

{1, 6}, {2, 3}, {2, 6},

{3, 4}, {3, 6}, {4, 6},

{5, 6}, {6, 6}, {6, 7}