Consider a natural number N and the expression H_N = 1 + (1/2) + (1/3) + ... + (1/N). Here (X/Y) illustrates division.

Determine the natural numbers, the numerator P and the denominator Q of the irreducible fraction H_N = P/Q

Input

The input contains on the first line the number N (2 ≤ N ≤ 10000).

Output

The output will contain on the first line the number P and on the second line the number Q.

Constraints

Time limit: 1 second
Memory limit: 128 megabytes

Examples

input
6

output
49
20

input
20

output
55835135
15519504

input
47

output
280682601097106968469
63245806209101973600

Explanation of the first example: 1 + (1/2) + (1/3) + (1/4) + (1/5) + (1/6) = (49/20)