0196. Strange things

Input file name:	strange.in
Output file name:	strange.out
Time limit:	2 s
Memory limit:	32 megabytes

Long time ago one famous scientist constructed the strange function and the strange sequence. He took some integer positive number N and wrote the following sequence: A₁ = F(2N,1), A₂ = F(2N,3), A₃ = F(2N,5) …A_N = F(2N,2N-1) where F(P,Q) is a strange function, which was constructed by the following rules:

1. For each integer positive number Q : F(0,Q) = 0
2. For each integer non-negative number P : F(P,0) = 1
3. Otherwise F(P,Q) = F(P-1,Q-1) + F(P-1,Q)

But the primary goal of his research was the strange function X(N). He denoted by X(N) the greatest common divisor of the numbers A₁…A_N. He finished exploring this problem after some years of unsuccessful attempts. So, as you understand, your task is quite simple. You have to calculate function X(N) for a given positive integer N.

Input file

Input file contains one integer number N (1 ≤ N ≤ 10¹⁰⁰⁰⁰).

Output file

You must output X(N).

Examples:

strange.in	strange.out
1	2

Source: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Discuss       Submit a solution