// 시간 초과, 테케 13/14 실패
function solution(n) {
  const fib = (n) => {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return (fib(n - 1) + fib(n - 2)) % 1234567;
  };
  return fib(n);
}

// +9 문제 오류였음 : 피보나치 결과를 나눠서 push
// 시간 : O(n) 공간 : O(1)
function solution(n) {
  const fib = [0, 1];

  for (let i = 0; i < n - 1; i++) {
    fib.push((fib[i] + fib[i + 1]) % 1234567);
  }
  return fib.pop();
}