함께 블록 쌓기
면접 대비시간 제한1초메모리 제한256 MB
N명의 학생이 각각 서로 다른 높이의 블록을 여러 개 가지고 있을 때, 학생마다 최대 하나의 블록을 골라 높이의 합이 정확히 H가 되는 경우의 수를 10007로 나눈 나머지로 구한다.
문제
1번부터 N번까지의 학생들은 각각 블록을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 학생이 가진 블록들의 높이는 모두 다르다. 1번부터 N번까지의 학생들이 가진 블록을 순서대로 사용해 바닥부터 쌓아 올려 하나의 탑을 만들려고 한다.
어떤 학생의 블록은 사용하지 않아도 되며, 한 학생당 최대 1개의 블록만 사용할 수 있다.
1번부터 N번까지의 학생들이 가진 블록 정보가 주어졌을 때, 높이가 정확히 H인 탑을 만들 수 있는 경우의 수를 계산하는 프로그램을 작성하시오.
예를 들어 N=3, M=3, H=5이고 각 학생이 가진 블록의 높이가 다음과 같다고 하자.
- 1번 학생: 2, 3, 5
- 2번 학생: 3, 5
- 3번 학생: 1, 2, 3
이때 탑의 높이가 정확히 5가 되도록 블록을 쌓는 경우는 다음 6가지이다. 블록을 사용하지 않는 학생은 X로 표시했다.
입력
첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐 각 학생이 가진 블록들의 높이가 공백을 기준으로 구분되어 주어진다.
모든 블록의 높이는 1,000 이하의 자연수이며, 한 학생이 가진 블록들의 높이는 모두 다르게 주어진다.
출력
첫째 줄에 높이가 H인 탑을 만드는 경우의 수를 10,007로 나눈 나머지를 출력한다.