#include <stdio.h>
int fib1(int n){
	int a,b,c,i;
	a=0;
	b=1;
	for(i=2;i<=n;i++){
	c=a+b;
	a=b;
	b=c;
	}
	return c;
}
 
int fib2(int n){
	int f[47],i;
	f[0]=0;
	f[1]=1;
	for(i=2;i<=n;i++){
	 f[i]=f[i-1]+f[i-2];
	}
	return f[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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CmludCBmaWIxKGludCBuKXsKCWludCBhLGIsYyxpOwoJYT0wOwoJYj0xOwoJZm9yKGk9MjtpPD1uO2krKyl7CgljPWErYjsKCWE9YjsKCWI9YzsKCX0KCXJldHVybiBjOwp9CgppbnQgZmliMihpbnQgbil7CglpbnQgZls0N10saTsKCWZbMF09MDsKCWZbMV09MTsKCWZvcihpPTI7aTw9bjtpKyspewoJIGZbaV09ZltpLTFdK2ZbaS0yXTsKCX0KCXJldHVybiBmW25dOwp9CgppbnQgZmliMyhpbnQgbil7CglpZihuPT0wKQoJcmV0dXJuIDA7CgllbHNlIGlmKG49PTEpCglyZXR1cm4gMTsKCWVsc2UKCXJldHVybiBmaWIzKG4tMSkrZmliMyhuLTIpOwp9CgppbnQgbWFpbih2b2lkKSB7CglpbnQgbjsKCXNjYW5mKCIlZCIsJm4pOwoJcHJpbnRmKCIxOiVkXG4iLGZpYjEobikpOwoJcHJpbnRmKCIyOiVkXG4iLGZpYjIobikpOwoJcHJpbnRmKCIzOiVkXG4iLGZpYjMobikpOwoJcmV0dXJuIDA7Cn0K

NQ==

5