The boy loves Dima bit operations with numbers, because they are fast, and does not like the modulus operation, because it is slow. He knows that if an integer N - power of two, then x % N = x (N-1) for any positive integer x, where — bitwise AND, and % — aking the modulo. He wants to extend this to other N and now wants to know for what proportion of the numbers x (1 ≤ x ≤ 10^100·N!) this equality is true for the N.
In a single line - an integer N (2 ≤ N ≤ 10^18).
In a single line - the answer to the problem as an irreducible fraction p/q.