Artem vs. Mansur#7798
Artem had a sequence of numbers, where 1 \le n \le 100. This sequence satisfied the condition: 1 \le L \le x_1 \le x_2 \le \ldots \le x_n \le R \le 10^9, and the least common multiple (LCM) of these numbers was divisible by (1 \le a \le 10^9). However, Mansur came and stole the sequence , leaving Artem unable to recall the exact numbers. He only remembers the values of , , , and . Artem wants to reconstruct the sequence by first determining how many such sequences could exist with the given , , , and . Your task is to write a program to find this number.
The input consists of a single line with four positive integers, separated by spaces: , , , .
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.
Example 1
Example 2
For example, in the first test case, the valid sequences are:
{, }, {, }, {, },
{, }, {, }, {, },
{, }, {, }, {, }