0196. Strange things

Имя входного файла:	strange.in
Имя выходного файла:	strange.out
Ограничение по времени:	2 s
Ограничение по памяти:	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

Источник: Petrozavodsk Summer 2003. Saratov SU Contest, Wednesday, August 27

Обсудить       Отправить решение