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

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

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

Входные данные

Одно целое число n (1 ≤ n ≤ 1018) - количество ходов в игре.

Выходные данные

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

Пример

В примере, на первом ходу Алекс не угадает загаданную Марти зебру с вероятностью p1 = 3 / 4, а на втором с вероятностью p2 = 8 / 9. Поэтому вероятность, с которой Алекс не угадает ни одну из черных в белую полоску зебр, равна p = 2 / 3.