2124번 - 블록 쌓기

A×B×C 크기의 삼차원 공간이 있다. 이는 밑면의 넓이가 A×B 크기의 직사각형이고, 높이 제한이 C라는 의미이다. 이러한 공간 안에 1×1×1 크기의 블록을 쌓으려고 한다. 이때 다음의 두 조건이 만족되어야 한다.

1. 어떤 칸에 블록을 쌓을 때에, 그 칸의 왼쪽 칸보다 높게 쌓을 수는 없다.
2. 어떤 칸에 블록을 쌓을 때에, 그 칸의 위쪽 칸보다 높게 쌓을 수는 없다.

예를 들어서 A = 3, B = 5, C = 5일 때, 다음과 같은 식으로 블록을 쌓을 수 있다. 각 칸은 그 왼쪽 칸과 위쪽 칸 이하의 높이로 블록을 쌓았다. 아래의 예에서도 확인할 수 있듯, 블록을 쌓지 않는 칸이 있을 수도 있다.

A, B, C가 주어졌을 때, 블록을 쌓는 경우의 수를 구하는 프로그램을 작성하시오.

첫째 줄에 세 정수 A, B, C가 주어진다.

첫째 줄에 답을 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다.

• 1 ≤ A ≤ 20
• 1 ≤ B, C ≤ 6