Combined Linear Congruential Generators of Pseudorandom Numbers

Quido is currently preparing examples for his new book on cybersecurity. He is focusing on linear congruential generators of pseudorandom numbers in which moduli are primes. These generators have various interesting properties and Quido decided to study some particular classes of these generators. One such class is specified below.

We say that a positive integer is an odd-squarefree number if it is not divisible by square of any odd prime.
Let the abbreviation LCG stand for linear congruential generator. Let the abbreviation LCM stand for least common multiple.

Let Mmin, Mmax, R be three integers, such that 2 ≤ Mmin ≤ Mmax, 2 ≤ R. We say that a combined linear congruential generator L is an acceptable combined linear congruential generator (abbreviated as ACLCG) if and only if it satisfies all following conditions.

L consists of R linear congruential generators which moduli are M₁, M₂, ..., M_R.
All moduli M₁, M₂, ..., M_R are primes satisfying Mmin ≤ M_k ≤ Mmax, for all k = 1, 2, ..., R.
LCM(M₁−1, M₂−1, ..., M_R−1) = (M₁−1) × (M₂−1) × ... × (M_R−1) / 2^R−1.
None of the values M₁−1, M₂−1, ..., M_R−1 is an odd-squarefree number.

Let L₁ and L₂ be two ACLCGs, each of which consists of R linear congruential generators. Let T₁ be the set of the moduli of all LCGs in L₁, and let T₂ be the set of the moduli of all LCGs in L₂. We say that L₁ and L₂ are categorically different if and only if T₁ ≠ T₂.

The task

You are given the values of Mmin, Mmax and R. Find the number of categorically different ACLCGs.

Input

The input contains one text line with three positive integers Mmin, Mmax, R. The values of Mmin and Mmax represent the minimum and the maximum possible value of the moduli of all LCGs of which one ACLCG consists. The value R specifies the number of LCGs in the ACLCG.
It holds, 2 ≤ Mmin ≤ Mmax ≤ 2×10⁶, 2 ≤ R ≤ 8, (Mmax − Mmin) × R ≤ 180000.

Output

The output contains one text line with one integer, the number of categorically different ACLCGs. It does not exceed 11×10⁶.

Example 1

Input

150 260 3

Output

Comment
The moduli of all categorically different of ACLCGs are listed below. Each line contains the set of the moduli of one ACLCG.

{163, 197, 251}
{197, 199, 251}

Example 2

Input

100 200 2

Output

Comment
The moduli of all categorically different of ACLCGs are listed below. Each line contains the set of the moduli of one ACLCG.

{101, 127}
{101, 163}
{101, 199}
{151, 197}
{163, 197}
{197, 199}

Example 3

Input

2000 3000 4

Output

Comment
The moduli of all categorically different ACLCGs are listed below. Each line contains the set of the moduli of one ACLCG. The list is followed by another list showing the factorization of each respective modulus decreased by one, for all ACLCGs.

{2029, 2351, 2663, 2843}
{2053, 2351, 2663, 2843}
{2287, 2351, 2549, 2663}
{2287, 2351, 2663, 2843}
{2351, 2467, 2549, 2663}
{2351, 2467, 2663, 2843}
{2351, 2503, 2549, 2663}
{2351, 2503, 2663, 2843}
{2351, 2549, 2663, 2683}
{2351, 2549, 2663, 2719}
{2351, 2557, 2663, 2843}
{2351, 2593, 2663, 2843}
{2351, 2663, 2683, 2843}
{2351, 2663, 2719, 2843}
{2351, 2663, 2843, 2917}
{2351, 2663, 2843, 2953}

2028 =  2^2 . 3 . 13^2,   2350 =   2 . 5^2 . 47,   2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2052 =  2^2 . 3^3 . 19,   2350 =   2 . 5^2 . 47,   2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2286 =  2 . 3^2 . 127,    2350 =   2 . 5^2 . 47,   2548 =  2^2 . 7^2 . 13,  2662 =  2 . 11^3
2286 =  2 . 3^2 . 127,    2350 =   2 . 5^2 . 47,   2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2466 =   2 . 3^2 . 137,  2548 =  2^2 . 7^2 . 13,  2662 =  2 . 11^3
2350 =  2 . 5^2 . 47,     2466 =   2 . 3^2 . 137,  2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2502 =   2 . 3^2 . 139,  2548 =  2^2 . 7^2 . 13,  2662 =  2 . 11^3
2350 =  2 . 5^2 . 47,     2502 =   2 . 3^2 . 139,  2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2548 =  2^2 . 7^2 . 13,  2662 =  2 . 11^3,        2682 =  2 . 3^2 . 149
2350 =  2 . 5^2 . 47,     2548 =  2^2 . 7^2 . 13,  2662 =  2 . 11^3,        2718 =  2 . 3^2 . 151
2350 =  2 . 5^2 . 47,     2556 =  2^2 . 3^2 . 71,  2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2592 =  2^5 . 3^4,       2662 =  2 . 11^3,        2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2662 =   2 . 11^3,       2682 =  2 . 3^2 . 149,   2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2662 =   2 . 11^3,       2718 =  2 . 3^2 . 151,   2842 =  2 . 7^2 . 29
2350 =  2 . 5^2 . 47,     2662 =   2 . 11^3,       2842 =  2 . 7^2 . 29,    2916 =  2^2 . 3^6
2350 =  2 . 5^2 . 47,     2662 =   2 . 11^3,       2842 =  2 . 7^2 . 29,    2952 =  2^3 . 3^2 . 41

This section serves as a short remainder of the concepts discussed in the problem description above.

The length of the period (or period length) of a periodic infinite sequence (a₀, a₁, a₂, a₃, ... ) is the smallest positive integer p for which identity    a_k = a_p+k    holds for all k = 0,1,2, ... .

A linear congruential generator with parameters A, C, M, denoted by LCG(A, C, M), is an abstract or a physical device which produces a sequence of integers
     (x₀, x₁, x₂, x₃, ... ),    where
         x_i+1 ≡ ( A·x_i + C) mod M, (i ≥ 0),
         A and C are non-negative integers, M is a positive integer.
Number x₀ is called seed of the generator, number A, C, M is called multiplier, increment and modulus of LCG(A, C, M), respectively.

A combined linear congruential generator (abbreviated by CLCG), consisting of a sequence (LCG(A₁, C₁, M₁), LCG(A₂, C₂, M₂), ..., LCG(A_r, C_r, M_r) ) of r ≥ 2 linear congruential generators, is an abstract or a physical device which produces a sequence of integers
     (y₀, y₁, x₂, y₃, ... ),   where
         y_i = (x_1,i − x_2,i + x_3,i − ... + (−1)^r−1 x_r,i) mod (M₁−1), for all i ≥ 0,
         (x_k,0, x_k,1, x_k,2, ... ) is the sequence produced by LCG(A_k, C_k, M_k), k = 1,2, ..., r.

It is known that the maximum possible length of the period of a sequence produced by a CLCG is equal to
B := (M₁−1) × (M₂−1) × ... × (M_r−1) / 2^r−1
The necessary condition for B to be attained by the CLCG is the equality B = LCM(M₁−1, M₂−1, ..., M_r−1).
This necessary condition motivates property 3. in the definition of ACLCG.

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