#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;
}
 

I2luY2x1ZGUgPHN0ZGlvLmg+CmludCBmaWIxKGludCBuKXsKaW50IGY7CmZvcihpbnQgaT0yLGYxPTAsZjI9MTtpPD1uKzE7aSsrKXsKIGY9ZjErZjI7CiBmMj1mMTsKIGYxPWY7Cn0KcmV0dXJuIGY7Cn0KCmludCBmaWIyKGludCBuKXsKCWludCBhW24rMV07CglhWzBdPTA7CglhWzFdPTE7Cglmb3IoaW50IGk9MjtpPD1uO2krKyl7CgkJYVtpXT1hW2ktMV0rYVtpLTJdOwoJfQoJcmV0dXJuIGFbbl07Cn0KCmludCBmaWIzKGludCBuKXsKCQoJaWYobj09MCkgcmV0dXJuIDA7CgllbHNlIGlmKG49PTEpIHJldHVybiAxOwoJZWxzZSByZXR1cm4gZmliMyhuLTEpK2ZpYjMobi0yKTsKfQppbnQgbWFpbih2b2lkKSB7CglpbnQgbjsKIHNjYW5mKCIlZCIsJm4pOwogcHJpbnRmKCIxOiVkXG4iLGZpYjEobikpOwogcHJpbnRmKCIyOiVkXG4iLGZpYjIobikpOwogcHJpbnRmKCIzOiVkXG4iLGZpYjMobikpOwoJcmV0dXJuIDA7Cn0K

Nw==

7