Problem Background

During the military operation against Planet Y, the fleet encountered difficulties in capturing city $p$.

Problem Description

Xiao Yuan's fleet employs a sonic weapon for attacks, but the enemy's walls are made of a special material—Pulin, which weakens the sonic attacks.

We define the weakening factor $m$ as: when a sonic wave of intensity $n$ hits, the wave penetrating Pulin is weakened to an intensity of $n \bmod m$.

Now, Xiao Yuan has launched $r-l+1$ sonic waves of intensities $l!, (l+1)!, (l+2)! \dots (r-1)!, r!$. The enemy uses Pulin with a weakening factor of $k$. Xiao Yuan wants to know the maximum intensity of the weakened sonic waves.

The symbol $!$ denotes factorial, where $x! = 1 \times 2 \times \dots \times x$. For example, $4! = 1 \times 2 \times 3 \times 4$. Specifically, $0! = 1$.

Input Format

Three positive integers $l, r, k$, as described above.

Output Format

An integer $ans$, representing the maximum intensity.

Sample Input and Output

Input Sample #1

1 3 4

Output Sample #1

2

Input Sample #2

3 6 10

Output Sample #2

6

Input Sample #3

100 1000 911451407

Output Sample #3

911273936

Notes

Sample 1 Explanation

The final intensities are $1, 2, 2$, hence the output is $2$.

Sample 2 Explanation

The final intensities are $6, 4, 0, 0$, hence the output is $6$.

Data Range

For 20% of the data: $1 \le l \le r \le 20$, $1 \le k \le 10^2$.

For 50% of the data: $1 \le l \le r \le 2000$, $1 \le k \le 10^5$.

For 100% of the data: $1 \le l \le r \le 2 \times 10^6$, $1 \le k \le 10^{12}$.

见题面 Input 部分

见题面 Output 部分