#include <stdio.h>
#include <string.h>

#define MAXN 400

int St[MAXN], Dr[MAXN], Mij[MAXN], Mij2[MAXN];
int N, i, A[MAXN], Sol[MAXN];
char S[MAXN];
int prime[48]={2, 4, 8, 16, 32, 64, 128, 3, 9, 27, 81, 5, 25, 125, 7, 49, 11, 121, 13, 17, 19, 23, 29, 
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,73,79, 83,89,97,101,103,107,109,113,127,131,137,139,149};

inline void add(int A[], int B[])
{
      int i, t = 0;
      for (i=1; i<=A[0] || i<=B[0] || t; i++, t/=10)
              A[i] = (t += A[i] + B[i]) % 10;
      A[0] = i - 1;
}

void sub(int A[], int B[])
{
      int i, t = 0;
      for (i = 1; i <= A[0]; i++)
              A[i] += (t = (A[i] -= ((i <= B[0]) ? B[i] : 0) + t) < 0) * 10;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}


inline int cmp(int A[], int B[])
{
	if (A[0]<B[0]) return -1;
	if (A[0]>B[0]) return 1;
	int w;
	for (w = A[0]; w>0 && A[w]==B[w]; --w);
	if (A[w]<B[w]) return -1;
	if (A[w]>B[w]) return 1;
	return 0;
}

void div(int A[], int B)
{
      int i, t = 0;
      for (i = A[0]; i > 0; i--, t %= B)
              A[i] = (t = t * 10 + A[i]) / B;
      for (; A[0] > 1 && !A[A[0]]; A[0]--);
}

void prod(int A[], int B[])
{
      int i, j, t, C[MAXN];
      memset(C, 0, sizeof(C));
      for (i = 1; i <= A[0]; i++)
      {
              for (t=0, j=1; j <= B[0] || t; j++, t/=10)
                      C[i+j-1]=(t+=C[i+j-1]+A[i]*B[j])%10;
              if (i + j - 2 > C[0]) C[0] = i + j - 2;
      }
      memcpy(A, C, sizeof(C));
}

inline void ridic(int A[], int t)
{
	int Aux[MAXN];
	memset(Aux, 0, sizeof(Aux));
	Aux[0]=Aux[1]=1;
	for (int i=1; i<=t; ++i)
		prod(Aux, A);
	memcpy(A, Aux, sizeof(Aux));
}

inline bool verif(int t)
{
	int Mij[MAXN], Mij2[MAXN];
	memset(Sol, 0, sizeof(Sol));
	memset(Mij, 0, sizeof(Mij));
	memset(Mij2, 0, sizeof(Mij2));
	memset(St, 0, sizeof(St));
	memset(Dr, 0, sizeof(Dr));
	St[0]=St[1]=1;
	Dr[0]=A[0]/t + 2;
	Dr[Dr[0]]=1;
	while (cmp(St,Dr)<=0){
		memset(Mij, 0, sizeof(Mij));
		add(Mij, St);
		add(Mij, Dr);
		div(Mij, 2);
		memcpy(Mij2, Mij, sizeof(Mij2));
		ridic(Mij2, t);
		int r = cmp(Mij2, A);
		if (r == 0){
			memcpy(Sol, Mij, sizeof(Mij));
			return true;
		}
		else{
			memset(Mij2, 0, sizeof(Mij2));
			Mij2[0]=Mij2[1]=1;
			if (r==-1){
				add(Mij, Mij2);
				memcpy(St, Mij, sizeof(St));
			}
			else {
				sub(Mij, Mij2);
				memcpy(Dr, Mij, sizeof(Mij));
			}
		}
	}
	return false;
}

inline void afis(int A[])
{
	for (int i=A[0]; i>=1; --i)
		printf("%d", A[i]);
	printf("\n");
}

int main()
{
	freopen("numere2.in","r",stdin);
	freopen("numere2.out","w",stdout);

	fgets(S, MAXN, stdin);
	N = strlen(S);
	if (S[N]<='0') S[--N]=0;
	A[0] = N;
	for (i=1; i<=N; ++i)
		A[i]=S[N-i]-'0';

	int ans = 1;
	for (i=0; ans*prime[i] <= 150 && i<48; ++i)
		if (verif(prime[i])){
			if (i>0 && ans%prime[i-1]==0 && prime[i]%prime[i-1]==0)
				ans/=prime[i-1];
			ans*=prime[i];
		}

	verif(ans);
	afis(Sol);
	printf("%d\n", ans);

	return 0;
}