#include<iostream>

using namespace std;

int N;
int Vector[1001];

inline void Initializare(int Vector[], int N)
{
	for (int i = 0; i <= N; ++i) Vector[i] = -1;
}

inline int Fibo_Dinamic_Iterativ(int N)
{
	Vector[0] = 0;
	Vector[1] = 1;
	for (int i = 2; i <= N ; ++i) Vector[i] = Vector[i - 1] + Vector[i - 2];
	return Vector[N];
}

inline int Fibo_Dinamic_Recursiv(int N)
{
	if (Vector[N] == -1) // inseamna ca elementul din pozitia N al sirului lui fibo nu e calculat
	{
		if (N == 0 || N == 1) Vector[N] = N;
		else Vector[N] = Fibo_Dinamic_Recursiv(N - 1) + Fibo_Dinamic_Recursiv(N - 2);

	}
	return Vector[N];
}



inline void READ()
{
	cin >> N;
}

int main()
{
	READ();
	cout << Fibo_Dinamic_Iterativ(N);
	cout << endl;
	Initializare(Vector, N);
	cout << Fibo_Dinamic_Recursiv(N);
	system("pause");
	return 0;
}