#include <stdio.h>

int fib1(int n)
{
	int a=0,b=1,c;
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else
		for(int i=2; i<=n; a=b,b=c,i++)
			c = a + b;
			return c;
}

int fib2(int n)
{
	int f[47];
	f[0]=0;
	f[1]=1;
	for(int i=2; i<=n; i++){
		f[i]=f[i-2]+f[i-1];
	}
	return f[n];
}

int fib3(int n)
{
	if(n==0)
		return 0;
	else if(n==1)
		return 1;
	else
		return fib3(n-2)+fib3(n-1);
}


int main(void) {
	int n;
	
	scanf("%d",&n);
	
	printf("1: %d\n",fib1(n));
	printf("2: %d\n",fib2(n));
	printf("3: %d\n",fib3(n));
	
	return 0;
}