우선 res*=(arr[i]%M); 이라는 걸 풀어쓰면 res = res * (arr[i]%M); 이 됩니다. 그럼 res가 가지게 되는 값은 과연 M보다 작을까요? res가 M-1이고, arr[i]%M도 M-1이면, 이 값은 (M-1)^2이 되겠죠.

그럼 다음 루프에서 또 arr[i]%M이 M-1이면, 이번에는 res가 (M-1)^3이 되겠네요. 이런 식으로 res는 자꾸자꾸 커지려고 합니다. 오버플로우가 날 수 있겠죠.

(A*B)%M=((A%M)*(B%M))%M 이니까 만약 항이 많아지면

(A*B*C*D)%M=((A%M)*(B%M)*(C%M)*(D%M))%M이 되는거 아닌가요...

(A%M)*(B%M)*(C%M)*(D%M) 부분을 공식화 하려고 res를 썻는데 그것마저 오버플로우가 발생하나보군요.

다른 방법이 있을까요

중요한 건 저 문장은 (A*B)%M을 수행하는 게 아니라 A*(B%M)을 수행한다는 거죠. 그래서 전체 식의 값이 M보다 작다는 보장이 없습니다.

그리고 (A*B*C*D)%M이라고 해도 반드시 각각을 M으로 나눈 나머지를 곱해서 나눈 나머지가 되진 않습니다. 식 상으로는 맞지만, 실제로 컴퓨터가 연산할 때는 곱하는 순간에 오버플로우가 발생하기 때문에 원하는 대로 동작을 못 합니다. 이 문제의 경우 long long형이 M으로 나눈 나머지 둘을 곱하는 것까진 괜찮지만 여기에 다른 값이 하나라도 더 곱해지는 순간 바로 오버플로우가 발생합니다. 모든 곱셈 연산 후 바로 바로 모듈러를 해줘야 됩니다.

오오오 바로바로 연산을 해주니 답이 구해집니다.

좀 더 공부가 필요한 파트인 것 같군요

감사합니다!!