#include <stdio.h>
int fib1(int n){
     if(n==0){
        return 0;}
     if(n==1){
        return 1;}
     int a =0;
     int b =1;
     int c =0;
     for(int i=2;i<=n ;i++){
         c=a+b;
         a=b;
         b=c;
   }
     return c;
}
int fib2(int n){
     if(n==0){ 
        return 0;}
     if(n==1){
        return 1;}
    int f[n+1];
    f[0]=0;
    f[1]=1;
    for(int 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;}
     if(n==1){
        return 1;}
    return fib3(n-1)+fib3(n-2);
}
int main(void) {
   int n;
   scanf("%d",&n);
 
   printf("fib1:%d\n",fib1(n));
   printf("fib2:%d\n",fib2(n));
   printf("fib3:%d\n",fib3(n));
	// your code goes here
	return 0;
}