다항 계수
시간 제한2초메모리 제한256 MB
n과 m, 그리고 지수 k가 주어질 때 (1+x+...+x^n)^m 전개식에서 x^k의 계수를 1,000,000,009로 나눈 나머지로 구합니다.
문제
다항 정리(multinomial theorem)는 다항식의 거듭제곱을 전개하는 정리이며, 전개식의 계수를 다항 계수(multinomial coefficient)라고 한다. 여기서 다루는 다항식은 모든 항의 계수가 1인 경우이며, 아래는 그 예이다.
(1 + x + x2)3 = 1 + 3x + 6x2 + 7x3 + 6x4 + 3x5 + x6
다항 정리를 일반화하면 다음과 같이 쓸 수 있다.
(1 + x + ... + xn)m = a0x0 + a1x1 + ... + anmxnm
어떤 수 k(0 ≤ k ≤ n × m)가 주어졌을 때 xk의 계수 ak를 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 음이 아닌 정수 n(0 ≤ n ≤ 500), m(1 ≤ m ≤ 500), k가 주어진다.
출력
첫 번째 줄에 xk의 계수를 출력한다. 단, 수가 커질 수 있으므로 1,000,000,009로 나눈 나머지를 출력한다.
힌트
문제에 주어진 다항식을 푸는 방식 중 하나는 다음과 같다.
- 1 + x + x2의 계수를 표현
- x(1 + x + x2)의 계수를 표현
- x2(1 + x + x2)의 계수를 표현
- 1~3의 각 열을 더함 ≡ (1 + x + x2)2의 계수
- 4~6의 각 열을 더함 ≡ (1 + x + x2)3의 계수