파이썬의 int형은 고정된 크기가 아닙니다. 그 변수가 실제로 담고 있는 값의 크기에 따라 유동적으로 사용하는 메모리가 변합니다.

수가 매우 커지게 되면 그 수를 정확하게 표현하기 위해 점점 더 많은 메모리를 할당받게 되는데, 이 문제의 경우 무턱대고 모든 항의 값을 다 구하려고 하면 N에 비례하여 자릿수가 점점 늘어나기 때문에 총 사용하게 되는 공간 복잡도가 O(N^2)이 됩니다. 배열을 쓰지 않고 한정된 변수들 사이에서 돌려가면서 처리하면 공간 문제는 해결하겠지만 여전히 시간 복잡도가 O(N^2)이기 때문에 통과할 수 없습니다.

이 문제와 같이 "~로 나눈 나머지를 출력한다"는 문제는 거의 대부분 전체 답을 먼저 구하고 마지막에 나머지 연산을 한 번 하라는 것이 아니라, 연산 과정에서 모듈로의 성질을 이용하여 수를 계속 작게 유지할 수 있도록 배려를 해주는 것입니다. 안 그러면 수가 너무 커져서 계산 시간도 오래 걸릴 뿐만 아니라 파이썬처럼 bigint를 지원하지 않는 언어에서는 구현하는 것 자체가 매우 까다롭기 때문입니다.

15746으로 나눈 나머지가 중요하니까 arrs 배열에 15746으로 나눈 나머지만 저장해보세요

그렇게 하시면 메모리 초과가 아니라 정상적으로 틀렸습니다가 뜹니다

말씀해주신대로 15746을 나눈 나머지값을 저장해였습니다. 그런데 왜 틀렸습니다가 뜰까요? 반례를 못찾겠습니다 ㅠ

N=3일 때 틀리게 됩니다.

또한 N=1일 때 arrs[2]가 존재하지 않아 런타임 에러도 발생합니다.

아래와 같이 수정했는데 N=3일때 3이 나오는게 맞는 답이 아닌가요? 

네, 이대로 제출하면 맞습니다.

앗 해결되었습니다 감사합니다!!ㅎㅎ

정말 도움주셔서 감사드립니다