[Algorithm] 나머지 연산 modulo의 법칙

★문제의 답이 매우 큰 경우 그 답을 특정한 어떤 수로 나눈 나머지를 대신 출력하는 문제가 종종 있다. 이런 경우 써 먹을 수 있는 나머지 연산의 법칙이 있다

★나머지 연산의 법칙

1. (a+b) % M = (a % M + b % M) % M
2. (a-b) % M = (a % M - b % M) % M
3. (a*b) % M = (a % M * b % M) % M

★매번 나머지 연산을 수행할 때 마다 나머지를 취해 주면 된다.

★2번의 경우 a - b의 결과가 음수라면 나머지 연산의 결과도 음수로 나오게 된다. 이 경우 M값을 다시 더해주면 된다.