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

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 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⁷. 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⁴⁰.

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.
Link to public data set