## Counting linear congruential generators

We are interested in the number of linear congruential generators of the form xi+1=(Axi+C) mod M with good properties (i.e., the length of the period is maximal possible).

Consider that each of the parameters A, C, M is bounded from below and from above by given values. Count the number of linear congruential generators fulfilling:

• M has at least D divisors (for some given integer D)
• C and M are coprimes
• A-1 is divisible by each prime factor of M
• if 4 divides M then also 4 divides A-1
Note that two linear congruential generators are different if they differ in at least one of their parameters.

### Input

The input consists of four lines. The first line contains integers Amin, Amax. The second line contains integers Cmin, Cmax. The third line contains integers Mmin, Mmax. Each pair of integers is separated by a space. The fourth line contains integer D.
Values of Amax, Cmax and Mmax are not greater than 4 × 107. Moreover, 1 ≤ Amin ≤ Amax, 1 ≤ Cmin ≤ Cmax, 2 ≤ Mmin ≤ Mmax and 2 ≤ D ≤ Mmax.

### Output

The output is one line containing one integer - the number of feasible linear congruential generators xi+1=(Axi+C) mod M where Amin ≤ A ≤ Amax, Cmin ≤ C ≤ Cmax and Mmin ≤ M ≤ Mmax. The resulting number is not greater than 240.

### Example 1

Input
```1 3
1 3
3 4
2
```
Output
```4
```
There are four solutions:
A=1, C=1, M=3
A=1, C=2, M=3
A=1, C=1, M=4
A=1, C=3, M=4

### Example 2

Input
```2 5
6 6
5 9
2
```
Output
```0
```
There is no solution for the given parameters ranges.

### Example 3

Input
```3 7
3 5
8 12
4
```
Output
```2
```
There are two solutions:
A=5, C=3, M=8
A=5, C=5, M=8

### Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.