P9707 [KMOI R1] Sonic Wave Weapon.

In [Military Operation on Planet $Y$](/problem/P9709), the fleet encountered some difficulties when capturing City $p$.

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$.

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

One integer $ans$, representing the maximum intensity.

## 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