====== 다항 계수 ======

===== 풀이 =====
  * 문제를 바꿔쓰면, [0..n] 범위의 자연수 m개로 이루어진 튜플 중에서 합이 k가 되는 것의 개수를 세는 문제이다.
  * [[https://hellogaon.tistory.com/66|공식 풀이]]는 O(m*k)의 DP 이지만, 조합론적 방법으로 O(m+k)에 푸는 것이 가능하다. 풀이는 [[ps:tutorial:composition#상한이 주어진 경우|상한이 주어진 composition]] 참고
  * 이 문제에서는 k의 범위가 k<=m*n 으로 주어져 있으므로, 시간복잡도가 O(m*n)이 된다

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 16725. 다항 계수".

- Problem link: https://www.acmicpc.net/problem/16725
- Solution link: http://www.teferi.net/ps/problems/boj/16725

Tags: [combinatorics]
"""

from teflib import combinatorics


MOD = 1_000_000_009


def main():
    n, m, k = [int(x) for x in input().split()]
    print(combinatorics.count_compositions(k, m, MOD, hi=n))


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

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