Under construction

Still being built. Things may change

Harmonic number

Interview

Time limit1sMemory limit512 MB

Summary
Compute the numerator and denominator of the harmonic number H_N as an irreducible fraction for N up to 10000.
Level

Medium4 of 10

Topics
Math, Number theory, Implementation, Greedy
Solved
No attempts yet

Problem

For a natural number NN, consider HN=1+1/2+1/3+⋯+1/NH_N = 1 + 1/2 + 1/3 + \cdots + 1/N.

Find the natural numbers PP and QQ, the numerator and denominator of the irreducible fraction HN=P/QH_N = P/Q.

Input

The standard input contains the natural number NN on the first line.

Output

On the standard output, print PP on the first line and QQ on the second line.

Constraints

  • 2≤N≤100002 \le N \le 10000

Examples3

  1. Example 1

    Input
    6
    Expected output
    49
20

  2. Example 2

    Input
    20
    Expected output
    55835135
15519504

  3. Example 3

    Input
    47
    Expected output
    280682601097106968469
63245806209101973600