Background

In Military Operation on Planet $Y$, the fleet encountered some difficulties when capturing City $p$.

Problem Description

Xiao Yuan’s fleet uses sonic wave weapons to attack, but the opponent’s city walls are made of a special material—Pulin (pinyin), so the sonic attacks are not very effective.

We define the weakening coefficient $m$ as follows: when a sonic wave with intensity $n$ is received, after penetrating Pulin it will be weakened to a sonic wave with intensity $n\bmod m$.

Now Xiao Yuan fires $r-l+1$ sonic waves with intensities $l!,(l+1)!,(l+2)!\dots (r-1)!,r!$. The opponent uses Pulin with weakening coefficient $k$. Xiao Yuan wants to know, after weakening, what the maximum intensity among these sonic waves is.

The symbol $!$ here denotes factorial: $x!=1\times 2\times\dots\times x$. For example, $4!=1\times2\times3\times4$. In particular, $0!=1$.

Input Format

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

Output Format

One integer $ans$, representing the maximum intensity.

1 3 4

2

3 6 10

6

100 1000 911451407

911273936

Hint

Sample $1$ Explanation

The final intensities are $1,2,2$, so output $2$.

Sample $2$ Explanation

The final intensities are $6,4,0,0$, so output $6$.

Constraints

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

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

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

Translated by ChatGPT 5