No reference implementation in this language.

// Fibonacci with memoization, TypeScript reference.
// Reads N from stdin, caches fib(i) in a Map, writes fib(N) + newline.
// BigInt sidesteps the 2^53 precision limit of JS number for large N.
// Annotations are kept minimal so the same source also runs under plain
// `node` (TS type stripping varies by runner — tsx/bun handle it, older
// nodes don't). The Map's value type is documented in the comment instead.

const chunks = [];
process.stdin.on("data", (c) => chunks.push(c));
process.stdin.on("end", () => {
  const input = Buffer.concat(chunks).toString("utf8").trim();
  const n = Number.parseInt(input, 10);
  if (!Number.isFinite(n) || n < 0) {
    process.stderr.write("N must be a non-negative integer\n");
    process.exit(1);
  }
  // memo: Map<number, bigint>
  const memo = new Map();
  memo.set(0, 0n);
  memo.set(1, 1n);
  const fib = (k) => {
    const cached = memo.get(k);
    if (cached !== undefined) return cached;
    const v = fib(k - 1) + fib(k - 2);
    memo.set(k, v);
    return v;
  };
  process.stdout.write(fib(n).toString() + "\n");
});

// Fibonacci with memoization, Rust reference.
// Reads N from stdin, caches fib(i) in a HashMap<u32, u64>.
// u64 holds fib(N) for N up to 93 (fib(93) = 12200160415121876738).
use std::collections::HashMap;
use std::io::{self, Read, Write};

fn fib(k: u32, memo: &mut HashMap<u32, u64>) -> u64 {
    if let Some(&v) = memo.get(&k) {
        return v;
    }
    let v = fib(k - 1, memo) + fib(k - 2, memo);
    memo.insert(k, v);
    v
}

fn main() {
    let mut input = String::new();
    io::stdin().read_to_string(&mut input).expect("read stdin");
    let n: u32 = input
        .trim()
        .parse()
        .expect("N must be a non-negative integer");
    let mut memo: HashMap<u32, u64> = HashMap::new();
    memo.insert(0, 0);
    memo.insert(1, 1);
    let v = fib(n, &mut memo);
    let stdout = io::stdout();
    let mut out = stdout.lock();
    write!(out, "{}\n", v).expect("write stdout");
}

// Fibonacci with memoization, Go reference.
// Reads N from stdin, caches fib(i) in a map[int]uint64.
// uint64 holds fib(N) for N up to 93.
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func fib(k int, memo map[int]uint64) uint64 {
	if v, ok := memo[k]; ok {
		return v
	}
	v := fib(k-1, memo) + fib(k-2, memo)
	memo[k] = v
	return v
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	line, _ := reader.ReadString('\n')
	n, err := strconv.Atoi(strings.TrimSpace(line))
	if err != nil || n < 0 {
		fmt.Fprintln(os.Stderr, "N must be a non-negative integer")
		os.Exit(1)
	}
	memo := map[int]uint64{0: 0, 1: 1}
	fmt.Print(fib(n, memo), "\n")
}

"""Fibonacci with memoization, Python reference.

Reads N from stdin, caches fib(i) in a dict. Python ints are arbitrary
precision so no overflow concerns regardless of N.
"""
import sys


def main() -> None:
    n = int(sys.stdin.readline().strip())
    if n < 0:
        sys.stderr.write("N must be a non-negative integer\n")
        sys.exit(1)
    memo: dict[int, int] = {0: 0, 1: 1}

    def fib(k: int) -> int:
        if k in memo:
            return memo[k]
        v = fib(k - 1) + fib(k - 2)
        memo[k] = v
        return v

    sys.stdout.write(f"{fib(n)}\n")


if __name__ == "__main__":
    main()