#include <stdio.h>

// 1
int fib1(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int a = 0;
    int b = 1; 
    int next;
    
    for (int i = 2; i <= n; i++) {
        next = a + b;
        a = b;
        b = next;
    }
    return b;
}

// 2
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];
}

// 3
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("1: %d\n", fib1(n));
    printf("2: %d\n", fib2(n));
    printf("3: %d\n", fib3(n));
    
    return 0;
}