16725번 - 다항 계수

다항 정리(multinomial theorem)는 다항식의 거듭제곱을 전개하는 정리이며, 전개식의 계수를 다항 계수(multinomial coefficient)라고 한다. 우리가 다룰 다항식은 모든 항의 계수가 1인 경우이고, 아래는 그 예시이다.

(1 + x + x²)³ = 1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶

다항정리를 일반화 하면, 다음과 같이 나타낼 수 있다.

(1 + x + ... + xⁿ)^m = a₀x⁰ + a₁x¹ + ... + a_nmx^nm

어떤 수 k(0 ≤ k ≤ n × m)가 주어졌을 때 x^k의 계수 a_k를 구하는 프로그램을 작성하시오.

첫 번째 줄에 음이 아닌 정수 n(0 ≤ n ≤ 500), m(1 ≤ m ≤ 500), k가 주어진다.

첫 번째 줄에 x^k의 계수를 출력한다. 단, 수가 커질 수 있으므로 1,000,000,009로 나눈 나머지를 출력한다.

문제에 주어진 다항식을 푸는 방식 중 하나는 다음과 같다.

1. 1+ x + x²의 계수를 표현
2. x(1+ x + x²)의 계수를 표현
3. x²(1+ x + x²)의 계수를 표현
4. 1~3의 각 열을 더함 ≡ (1 + x + x²)²의 계수
7. 4~6의 각 열을 더함 ≡ (1 + x + x²)³의 계수