배열 세기

문제 정보

문제

2014 개정수학 수II의 함수 단원을 공부하던 수찬이는 반복적인 학습이 지겨워서, 문제집에서 다루지 않는 함수를 만들기로 했다!

수찬이는 자신의 이니셜을 딴 \texttt{sc}(A, x)라는 함수를 만들기로 했다. A[1..n]는 길이가 n인 자연수(1 이상의 정수)로 구성된 배열이고, x는 자연수이다.

수찬이는 이 함수를 어떻게 정의하면 좋을지 고민하다가, 우연히 지학이를 만났다. 지학이는 배열에 아래와 같은 연산을 하며 놀고 있었다.

  • 두 정수 lr (1 \le l \le r \le n)을 정한다.
  • A[l], A[l+1], \cdots, A[r-1], A[r]에 각각 1을 더한다.

수찬이는 이 모습을 보고, \texttt{sc}(A, x)를 이렇게 정의하기로 했다.

  • A[i] > x를 만족하는 i (1 \le i \le n)가 존재한다면 -1
  • 존재하지 않는다면, A의 모든 원소를 x로 만들기 위해 지학이의 연산을 해야 하는 최소 횟수

수찬이는 함수를 정의한 기념으로, \texttt{sc}(A, k) = l를 만족하는 길이가 n인 서로 다른 배열 A가 몇 개나 되는지 세고자 한다. 그러나 수찬이가 직접 세기에는 이러한 경우의 수가 너무나 많았다.

수찬이를 도와 경우의 수가 몇 개인지 세어 보자.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

이후, 각 테스트 케이스마다 n, k, c (1 \le n \le 5000, 1 \le k \le 2000, 1 \le c \le 100)가 공백을 사이로 두고 한 줄에 주어진다.

출력

각 테스트 케이스마다 한 줄에 c+1개의 음이 아닌 정수를 출력한다. 이 중 (l+1)번째 수 (0 \le l \le c)는 \texttt{sc}(A, k) = l를 만족하는 배열 A의 개수를 1,000,000,009 (= 10^{9} + 9)로 나눈 나머지여야 한다.

예제 입력

1
3 2 3

예제 출력

1 6 1 0

노트

  • \texttt{sc}(A, 2) = 0인 경우: [2, 2, 2]
  • \texttt{sc}(A, 2) = 1인 경우: [1, 1, 1], [1, 1, 2], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1]
  • \texttt{sc}(A, 2) = 2인 경우: [1, 2, 1]
  • \texttt{sc}(A, 2) = 3인 경우: 없음

어떤 두 배열 A[1..n]B[1..n]이 서로 다르다는 것은, A[i] \neq B[i] (1 \le i \le n)을 만족하는 i가 존재한다는 것과 같다.

3개의 댓글이 있습니다.