28669번 - Черные и белые 다국어

Марти уверен, что зебры в большинстве своем --- белые в черную полоску. Чтобы доказать, что черные в белую полоску зебры встречаются редко, Марти предложил Алексу сыграть в одну интересную игру.

Прямо сейчас они смотрят с холма на пастбище. Пастбище можно представить в виде бесконечного клетчатого поля, в каждой клетке которого стоит ровно одна зебра. Игра состоит из $n$ ходов, пронумерованных от $1$ до $n$: на $i$-м ходу Марти выбирает квадратный участок пастбища со стороной $i + 1$, ровно в одной клетке которого стоит зебра черная в белую полоску, а во всех остальных --- зебры белые в черную полоску. Алекс должен угадать, в какой клетке стоит черная в белую полоску зебра.

Каждый раз Марти выбирает квадрат, не пересекающийся ни с одним из выбранных ранее. Поскольку Алекс не умеет отличать белых в черную полоску зебр от черных в белую (да и как их вообще можно отличить?), каждый выбор он делает наугад, равновероятно выбирая случайную клетку в указанном квадрате. Найдите вероятность того, что Алекс не угадает ни одну из черных в белую полоску зебр.

В единственной строке дано одно целое число $n$ --- количество ходов в игре ($1 \le n \le 10^{18}$).

В единственной строке выведите два целых числа $p$ и $q$, разделенные пробелом --- числитель и знаменатель несократимой дроби, равной искомой вероятности.

В примере, на первом ходу Алекс не угадает загаданную Марти зебру с вероятностью $p_1 = \frac{3}{4}$, а на втором --- с вероятностью $p_2 = \frac{8}{9}$. Поэтому вероятность, с которой Алекс не угадает ни одну из черных в белую полоску зебр, равна $p = \frac{2}{3}$.