let dp = ref [ 1; 1 ]

let rec fib num =
  match num with
  | 0 -> List.nth !dp 0
  | 1 -> List.nth !dp 1
  | num ->
    try
      List.nth !dp num
    with Failure "nth" ->
      let x = fib (num - 2) + fib (num - 1) in
      dp := !dp @ [x];
      x


let () =
  let n = read_int () in
  print_int @@ fib n

