백준 15829 자바(모듈로 연산)

모듈로 연산이 뭔지 몰라서 애먹었다.모듈로 연산은 그냥 나머지 연산이라 이해하면 된다.%%

import java.util.*;
import java.io.*;
public class Main {

  
   
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        sc.nextLine();
        String str = sc.nextLine();
        long[] arr = new long[str.length()];

        for(int i=0;i<str.length();i++){
            arr[i] = str.charAt(i)-'a'+1;
        }

        long hash = 0;
        long pow = 1;
        long M = 1234567891;
        for(int i=0;i<arr.length;i++){
            hash = (hash+(arr[i]*pow))%M;
            pow = (pow*31)%M; // 여기가 중요함.
        }
        System.out.println(hash);
    }
}

문제에서 보면 M으로 모듈로 연산을 하라고 나와있다.왜 나머지 연산을 하는데 답이 맞다고 나오는거지?하고 의문을 가졌었는데 그냥 문제에 그러라고 나와있는거였다 좀 허무하다.

모듈로 연산을 하면 long형으로도 범위를 벗어나는 값의 범위를 다룰수 있다.모듈로 값보다 커지면 나눠질테니까

이해가 안 됐던건 이 부분이다.
hash = (hash+(arr[i]pow))%M;
pow = (pow31)%M; // 여기가 중요함.

분명 문제에는 최종값에 M을 나머지 연산하라 되어있는데 왜 저런 식을 사용해도 답이 맞는거지?의문이 들었다.근데 이건 그냥...단순한 분배법칙이었다.최종값에 모듈로 연산을 하나 그 전 식들에 분배해서 하나 값은 똑같다는 거였다.