#include <stdio.h>

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

int fib2(int n) {
    int a[50], i;

    a[0] = 0;
    a[1] = 1;
    for(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() {
   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;
}