시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 7 2 40.000%

문제

A×B×C(1≤A≤20, 1≤B, C≤6) 크기의 삼차원 공간이 있다. 이는 밑면의 넓이가 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 1 1

예제 출력

2

힌트