#include <stdio.h>
int fib1(int n){
int f;
for(int i=2,f1=0,f2=1;i<=n+1;i++){
 f=f1+f2;
 f2=f1;
 f1=f;
}
return f;
}

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

int fib3(int n){
	
	if(n==0) return 0;
	else if(n==1) return 1;
	else return fib3(n-1)+fib3(n-2);
}
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;
}