Problem E
Plan Your Guesses
After the Deer God heals Ashitaka in the forest, Ashitaka gives San a challenge to distract himself. He tells San that his favorite number is between $1$ and $n$, and wants her to guess it.
Anytime San guesses a number, she will be told that the guess is correct, or that it is too high or too low. Additionally, in each guess, she can only pick a feasibly correct answer. For example, if her guess of $5$ was too low, she can no longer guess any number between $1$ and $5$.
To make this more fun, San recalls her two favorite numbers $l$ and $m$, and challenges herself to guess Ashitaka’s favorite number in $l$ mod $m$ guesses. Moro is amused by how silly the game is, and decides to partake by finding the probability that San succeeds in her challenge, knowing that San will make the guesses that maximize her chances of winning.
Given $n$, $m$, and $l$, help Moro find this probability!
Input
There is one line of input containing the three space-separated integers $n \: (1 \leq n \leq 10^{15})$, $m \: (1 \leq m \leq 50)$, and $l \: (0 \leq l \leq m-1)$. $n$ represents the size of your list of numbers, whereas $m$ and $l$ represent that you are trying to achieve a number of guesses that is $l$ more than a multiple of $m$.
Output
If the maximal probability is the fraction $\frac{a}{b}$, where $a$ and $b$ are relatively prime, then output one line containing the integers $a$ and $b$, space separated.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 2 1 |
5 7 |
