## Counting linear congruential generators

We are interested in the number of linear congruential generators of the form x

_{i+1}=(Ax

_{i}+C) mod M with good properties (i.e., the length of the period is maximal possible).

### The task

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

### Input

The input consists of four lines. The first line contains integers A_{min}, A_{max}. The second line contains integers C_{min}, C_{max}.
The third line contains integers M_{min}, M_{max}. Each pair of integers is separated by a space. The fourth line contains integer D.

Values of A_{max}, C_{max} and M_{max} are not greater than 4 × 10^{7}. Moreover, 1 ≤ A_{min} ≤ A_{max},
1 ≤ C_{min} ≤ C_{max}, 2 ≤ M_{min} ≤ M_{max} and 2 ≤ D ≤ M_{max}.

### Output

The output is one line containing one integer - the number of feasible linear congruential generators x_{i+1}=(Ax_{i}+C) mod M where
A_{min} ≤ A ≤ A_{max}, C_{min} ≤ C ≤ C_{max} and M_{min} ≤ M ≤ M_{max}.
The resulting number is not greater than 2^{40}.

### Example 1

**Input**

1 3 1 3 3 4 2

**Output**

4There 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**

0There is no solution for the given parameters ranges.

### Example 3

**Input**

3 7 3 5 8 12 4

**Output**

2There 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.

**Link to public data set**