Counting linear congruential generators

A linear congruential generator (LCG) is a triple of integers (A, C, M) used to generate pseudorandom numbers by the formula x_n+1=(Ax_n+C) mod M applied recurrently to a chosen initial value x₀.

The task

By the assumption that there are ranges specified for the parameters A, C, M, count the number of full length period LCGs for which M is the product of exactly P distinct primes (where P is a given number).

Hint: It might be helpful to use the inclusion-exclusion principle.

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 an integer P. The following limits hold:
1 ≤ A_min ≤ A_max ≤ 3 × 10¹¹, 1 ≤ C_min ≤ C_max ≤ 3 × 10¹¹, 1 ≤ M_min ≤ M_max ≤ 2 × 10¹⁰, M_max ≤ A_max, 2 ≤ P ≤ 9.

Output

The output consists of one line containing integer R which is equal to the number of LCGs (A, C, M) that meet the following conditions:

A_min ≤ A ≤ A_max,
C_min ≤ C ≤ C_max,
M_min ≤ M ≤ M_max,
M is the product of P distinct primes,
(A, C, M) has period of length M.

It holds that R does not exceed 5 × 10¹⁶.

Example 1

Input

Output

The two feasible LCGs are as follows:

A=7, C=5, M=6
A=13, C=5, M=6

Example 2

Input

Output

The fourteen feasible LCGs are as follows:

A=31, C=23, M=30
A=31, C=29, M=30
A=61, C=23, M=30
A=61, C=29, M=30
A=91, C=23, M=30
A=91, C=29, M=30
A=121, C=23, M=30
A=121, C=29, M=30
A=43, C=23, M=42
A=43, C=25, M=42
A=43, C=29, M=42
A=85, C=23, M=42
A=85, C=25, M=42
A=85, C=29, M=42

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