Marty is sure that most zebras are white with black stripes. To prove that black and white striped zebras are rare, Marty suggested that Alex play an interesting game.

Right now they are looking down from the hill towards the pasture. A pasture can be represented as an endless checkered field, in each cell there is exactly one zebra. The game consists of n moves, numbered from 1 to n: on the i-th move, Marty chooses a square piece of pasture with side i + *1 *, in exactly one cell of which there is a black zebra with a white stripe, and in all the rest there are white zebras with a black stripe. Alex has to guess which cell contains the black and white striped zebra.

Each time, Marty chooses a square that does not intersect with any of the previously selected squares. Since Alex can't differ white-striped zebras from black-striped zebras (and how can they be distinguished at all?), he makes each choice at random, choosing a random cell in the indicated square with equal probability. Find the probability that Alex does not match any of the black and white striped zebras.

Input

One integer n (1 ≤ n ≤ 1018) - the number of moves in the game.

Output

Print two integers p and q, space-separated numerator and denominator of an irreducible fraction equal to the desired probability.

Examnple

In the example, on the first move Alex will not guess the zebra that Marty has guessed with probability p1 = 3 / 4, and on the second move with probability p2 = 8 / 9. Therefore, the probability that Alex will not guess any of the black and white striped zebras is p = 2 / 3.