시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 73 28 19 38.000%

문제

다항 정리(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

2 3 4

예제 출력 1

6

노트

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

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