Мальчик Дима любит битовые операции с числами, потому что они быстрые, и не любит операцию взятия по модулю, потому что она медленная. Он знает, что если целое число N — степень двойки, то x % N = x (N-1) для любого натурального x, где — побитовое И, а % — взятие по модулю. Он хочет распространить это на другие числа N и теперь хочет узнать, для какой доли чисел x (1 ≤ x ≤ 10^100·N!) это равенство будет верно для данного N.
В единственной строке — целое число N (2 ≤ N ≤ 10^18).
В единственной строке — ответ на задачу в виде несократимой дроби p/q.