====== 이항 계수 4 ======

===== 풀이 =====
  * 모듈러스가 n보다 작은 소수일 경우의 이항 계수를 구하는 문제. 뤼카의 정리를 이용해서 푼다.
  * 자세한 풀이는 [[ps:이항 계수#모듈러스가 n보다 작은 소수일 때|이항 계수 - 모듈러스가 n보다 작은 소수일 때]]를 참고.
  * 위의 링크에도 언급되어 있지만, C(n_i, k_i)를 계산하는 함수가, n_i < k_i 인 경우를 처리하는지 주의 할 것.

===== 코드 =====
<dkpr py>
from teflib import combinatorics


def main():
    N, K, M = [int(x) for x in input().split()]
    comb_table = combinatorics.CombTable(M - 1, M)
    answer = 1
    while N > 0:
        N, n_mod = divmod(N, M)
        K, k_mod = divmod(K, M)
        answer *= comb_table.get(n_mod, k_mod)

    print(answer % M)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:combinatorics#CombTable|teflib.combinatorics.CombTable]]

{{tag>BOJ ps:problems:boj:플래티넘_5}}