마지막 결과만 나머지를 구하면 되는 것이 아니고, 중간 과정에서도 나머지를 해서 오버플로우가 발생하지 않게 만들어야 합니다.

참고로 100만번째 피보나치 수의 실제 값은 약 20만 자리의 수입니다.

중간 과정에서 나머지를 해도 값이 바뀌지 않는 이유가 어째서 그런건지 이해가 잘 안갑니다 ㅜㅜ

문제 해결은 됐습니다! 생각해보니 최종값에 15746 나머지연산자를 하는거면 그 전값에 다 해도 똑같네요

만일 덧셈으로만 이루어진 식에서 마지막 값의 1의 자리의 수를 구한다고 하면, 10의 자리 이상은 무시하고 1의 자리만 계속 유지하면서 진행해도 됩니다. 그것은 중간 결과를 계속 10으로 나눈 나머지를 가지고 진행하는 것과 같습니다. 마찬가지로, 15746진법으로 수를 표현해서 진행할 때 마지막 1의 자리의 수를 구하는 것이 목표라면 마지막 1의 자리만 유지하면서 진행해도 되고, 이는 15746으로 나눈 나머지를 가지고 진행하는 것과 같습니다.

맞네요 이해 바로 갔습니다 감사합니다.