https://www.acmicpc.net/problem/11401  이항 계수 3이라는 문제를 풀었는데, 여기서 사용된 수학 개념과 테크닉은 향후 유용하겠다 싶어서 정리한다. 사용되는 기법유클리드 호제법페르마의 소정리O(logN) 거듭제곱 모듈로 계산(분할 정복)다이나믹 프로그래밍 문제의 접근문제는 매우 간단하다. 이항 계수를 1e9+7로 나눈 나머지를 구하면 된다. 일반적으로 이항 계수를 구하는 방법은 다음과 같이 팩토리얼을 이용한다. 여기서 MOD 연산이추가되어야 할 것이다. 최대 400만 팩토리얼을 구해야 하기 때문에 MOD를 통해 줄여야 한다.  우선 여기까진 당연히 맞다. 그러면 계산을 다음과 같이 해야할까? 아니다. 뭔가 이상하다. modulo 연산은 다음과 같이 덧셈(=뺄셈)과 곱셈에만 적..