var memo = hashMapOf<Int, Int>();

fun fib(n: Int): Int {
    
    if (memo.containsKey(n)) {
        return memo[n]!!
    }
    
    var result: Int
    
    if (n <= 2) {
        result = 1
    } else {
        result = fib(n - 1) + fib(n - 2)
    }
    
    memo[n] = result
    return result
}

fun main() {
    for (i in 1..10) {
    	println(fib(i))    
    }
}