블록 쌓기
시간 제한2초메모리 제한128 MB
각 칸의 높이가 0부터 C 사이이고 행과 열 방향으로 모두 감소하지 않는(왼쪽, 위쪽 칸보다 크지 않은) A×B 격자의 개수를 1,000,000,000,000,000,000으로 나눈 나머지로 구합니다.
문제
크기가 A x B x C인 직육면체 공간이 있다. 바닥은 A행 B열 격자이고, 각 칸에는 0개 이상 C개 이하의 1 x 1 x 1 블록을 수직으로 쌓을 수 있다.
각 칸의 높이는 다음 조건을 만족해야 한다.
- 왼쪽 칸이 있는 경우, 현재 칸의 높이는 왼쪽 칸의 높이보다 클 수 없다.
- 위쪽 칸이 있는 경우, 현재 칸의 높이는 위쪽 칸의 높이보다 클 수 없다.
블록을 하나도 놓지 않는 칸도 허용된다. A, B, C가 주어질 때 가능한 블록 배치의 수를 구하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
가능한 블록 배치의 수를 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.
제한
- 1 <= A <= 20
- 1 <= B, C <= 6